#ifndef __SBCTN_H__
#define __SBCTN_H__

#if _MSC_VER
#pragma once
#pragma warning(push)
#pragma warning(disable:4127)
#pragma warning(disable:4200)
#endif

#include "sbcs.h"
#include "sbtpl.h"

K_EXTERN_C_BEGIN

//////////////////////////////////////////////////////////////////////////
// array
typedef struct kArr
{
	kbyte*				data;
	kssize_t			count;
	kssize_t			capa;
} kArr;

#define K_ARR_DECL(name,type)\
	typedef struct name name;\
	typedef type name##Type;\
	struct name { type* data; kssize_t count; kssize_t capa; };

#define k_arr_nth(p,n)						(((p)->data)[(kssize_t)(n)])
#define k_arr_inv(p,n)						(((p)->data)[((p)->count-1-(kssize_t)(n))])
#define k_arr_count(p)						((p)->count)
#define k_arr_capacity(p)					((p)->capa)
#define k_arr_data(p)						((p)->data)
#define k_arr_sizeof(name)					(sizeof(name##Type))
#define k_arr_is_empty(p)					((p)->count==0)
#define k_arr_is_have(p)					((p)->count!=0)

#define k_arr_init(name,p,initcapa)\
	K_STMT_BEGIN{\
		(p)->data=NULL;\
		(p)->count=0;\
		(p)->capa=0;\
		if ((initcapa)>0)\
			k_arr_inl_expand((kpointer)(p), k_arr_sizeof(name), (initcapa));\
	}K_STMT_END

#define k_arr_disp(name,p)\
	K_STMT_BEGIN{ k_free((p)->data); }K_STMT_END

#define k_arr_set_capacity(name,p,newcapa)\
	K_STMT_BEGIN{ k_arr_inl_expand((kpointer)(p), k_arr_sizeof(name), newcapa); }K_STMT_END

#define k_arr_set_count(name,p,newcnt)\
	K_STMT_BEGIN{ k_arr_inl_expand((kpointer)(p), k_arr_sizeof(name),(newcnt)); (p)->count=(newcnt); }K_STMT_END

#define k_arr_copy(name,p,o)\
	K_STMT_BEGIN{\
		if (!(o) || !(o)->count)\
			(p)->count=0;\
		else\
		{\
			kssize_t __n=(o)->count;\
			k_arr_set_count(name,p,__n);\
			memcpy((p)->data, (o)->data, __n*k_arr_sizeof(name));\
		}\
	}K_STMT_END

#define k_arr_blob(name,p,items,cnt)\
	K_STMT_BEGIN{\
		if ((kssize_t)(cnt)>0)\
		{\
			k_arr_inl_expand((kpointer)(p), k_arr_sizeof(name), (p)->count+(kssize_t)(cnt));\
			memcpy(&k_arr_nth(p, (p)->count), (items), k_arr_sizeof(name)*(kssize_t)(cnt));\
			(p)->count+=(kssize_t)(cnt);\
		}\
	}K_STMT_END

#define k_arr_remove_nth(name,p,n)\
	K_STMT_BEGIN{\
		k_assert((kssize_t)(n)<(p)->count, "remove index overflow!");\
		{\
			name##Type* __t=&k_arr_nth(p,n);\
			if ((kssize_t)(n)!=(p)->count-1)\
				memmove(__t, __t+1, k_arr_sizeof(name)*((p)->count-((kssize_t)(n)+1)));\
			(p)->count--;\
		}\
	}K_STMT_END

#define k_arr_remove_range(name,p,idx,cnt)\
	K_STMT_BEGIN{\
		kssize_t __s=(kssize_t)(idx)+(kssize_t)(cnt);\
		kssize_t __cnt=(p)->count;\
		if ((kssize_t)(idx)<__cnt && __s<__cnt)\
		{\
			if (__s!=__cnt-1)\
				memmove(&k_arr_nth(p,idx), &k_arr_nth(p,__s), (__cnt-__s)*k_arr_sizeof(name));\
			(p)->count-=(kssize_t)cnt;\
		}\
	}K_STMT_END

#define k_arr_clear(name,p)\
	((p)->count=0)

#define k_arr_find(name,p,start,func_ud_ptr,userdata,ret)\
	K_STMT_BEGIN{\
		kssize_t __i, __cnt=(p)->count;\
		for (*(ret)=-1, __i=(kssize_t)(start); __i<__cnt; __i++)\
		{\
			if (func_ud_ptr(userdata, &k_arr_nth(p,__i)))\
			{\
				*(ret)=__i;\
				break;\
			}\
		}\
	}K_STMT_END

#define k_arr_sort(name,p,func)\
	(k_qsort((p)->data, (p)->count, k_arr_sizeof(name), func))

#define k_arr_sort_context(name,p,func,userdata)\
	(k_qsort_context((p)->data, (p)->count, k_arr_sizeof(name), func, userdata))

/* value type */
#define k_arr_add(name,p,item)\
	K_STMT_BEGIN{\
		if ((p)->count>=(p)->capa)\
			k_arr_inl_expand((kpointer)(p), k_arr_sizeof(name), (p)->capa+1);\
		k_arr_nth(p,(p)->count)=(item);\
		(p)->count++;\
	}K_STMT_END

#define k_arr_reserve(name,p)\
	K_STMT_BEGIN{\
		if ((p)->count>=(p)->capa)\
			k_arr_inl_expand((kpointer)(p), k_arr_sizeof(name), (p)->capa+1);\
		(p)->count++;\
	}K_STMT_END

#define k_arr_insert(name,p,idx,item)\
	K_STMT_BEGIN{\
		if ((kssize_t)(idx)<=(p)->count)\
		{\
			if ((p)->count>=(p)->capa)\
				k_arr_inl_expand((kpointer)(p), k_arr_sizeof(name), (p)->capa+1);\
			memmove((p)->data+(kssize_t)(idx)+1, (p)->data+(kssize_t)(idx), ((p)->count-(kssize_t)(idx))*k_arr_sizeof(name));\
			k_arr_nth(p,idx)=(item);\
			(p)->count++;\
		}\
	}K_STMT_END

#define k_arr_remove(name,p,item)\
	K_STMT_BEGIN{\
		kssize_t __i, __cnt=(p)->count;\
		for (__i=0; __i<__cnt; __i++)\
		{\
			if (k_arr_nth(p,__i)==(item))\
			{\
				name##Type* __t=&k_arr_nth(p,__i);\
				memmove(__t, __t+1, k_arr_sizeof(name)*(__cnt-(__i+1)));\
				__cnt--;\
				break;\
			}\
		}\
		(p)->count=__cnt;\
	}K_STMT_END

#define k_arr_remove_cmp(name,p,func_ptr_item,item)\
	K_STMT_BEGIN{\
		kssize_t __i, __cnt=(p)->count;\
		for (__i=0; __i<__cnt; __i++)\
		{\
			name##Type* __t=&k_arr_nth(p,__i);\
			if (func_ptr_item(__t,(item)))\
			{\
				memmove(__t, __t+1, k_arr_sizeof(name)*(__cnt-(__i+1)));\
				__cnt--;\
				break;\
			}\
		}\
		(p)->count=__cnt;\
	}K_STMT_END

#define k_arr_contains(name,p,item,retintptr)\
	K_STMT_BEGIN{\
		kssize_t __i, __cnt=(p)->count;\
		for (*(retintptr)=-1, __i=0; __i<__cnt; __i++)\
		{\
			if (k_arr_nth(p,__i)==(item))\
			{\
				*(retintptr)=(int)__i;\
				break;\
			}\
		}\
	}K_STMT_END

#define k_arr_contains_cmp(name,p,func_ptr_item,item,retintptr)\
	K_STMT_BEGIN{\
		kssize_t __i, __cnt=(p)->count;\
		for (*(retintptr)=-1, __i=0; __i<__cnt; __i++)\
		{\
			if (func_ptr_item(&k_arr_nth(p,__i),(item)))\
			{\
				*(retintptr)=(int)__i;\
				break;\
			}\
		}\
	}K_STMT_END

#define k_arr_foreach(name,p,func_ud_ptr,userdata)\
	K_STMT_BEGIN{\
		kssize_t __i, __cnt=(p)->count;\
		for (__i=0; __i<__cnt; __i++)\
			func_ud_ptr(userdata, &k_arr_nth(p,__i));\
	}K_STMT_END

#define k_arr_loopeach(name,p,func_ptr)\
	K_STMT_BEGIN{\
		kssize_t __i, __cnt=(p)->count;\
		for (__i=0; __i<__cnt; __i++)\
			func_ptr(&k_arr_nth(p,__i));\
	}K_STMT_END

K_INLINE void k_arr_inl_expand(kpointer arr, kssize_t size, kssize_t cnt)
{
	kArr* p=(kArr*)arr;
	if (p->count<cnt)
	{
		p->capa=p->capa+p->capa/2;
		if (p->capa<cnt)
			p->capa=cnt;
		p->data=k_renew(p->data, p->capa*size, kbyte);
	}
}


//////////////////////////////////////////////////////////////////////////
// pointer array
K_ARR_DECL(kPtrArr, kpointer);

#define k_parr_nth(p,i)				k_arr_nth(p,i)
#define k_parr_count(p)				k_arr_count(p)
#define k_parr_capacity(p)			k_arr_capacity(p)
#define k_parr_is_empty(p)			k_arr_is_empty(p)
#define k_parr_is_have(p)			k_arr_is_have(p)

#define k_parr_init(p, capacity)\
	k_arr_init(kPtrArr, p, capacity)

#define k_parr_disp(p)\
	k_arr_disp(kPtrArr, p)

#define k_parr_clear(p)\
	k_arr_clear(kPtrArr, p)

#define k_parr_set_capacity(p,capa)\
	k_arr_set_capacity(kPtrArr, p, capa)

#define k_parr_set_count(p,count)\
	k_arr_set_count(kPtrArr, p, count)

#define k_parr_remove_nth(p, index)\
	k_arr_remove_nth(kPtrArr, p, index)

#define k_parr_remove_range(p, index, count)\
	k_arr_remove_range(kPtrArr, p, index, count)

#define k_parr_remove(p, item)\
	k_arr_remove(kPtrArr, p, item)

#define k_parr_add(p, item)\
	k_arr_add(kPtrArr, p, item)

#define k_parr_reserve(p)\
	k_arr_reserve(kPtrArr, p)

#define k_parr_insert(p, index, item)\
	k_arr_insert(kPtrArr, index, item)

#define k_parr_sort(p, func)\
	k_arr_sort(kPtrArr, p, func)

#define k_parr_sort_context(p, func, userdata)\
	k_arr_sort_context(kPtrArr, p, func, userdata)

#define k_parr_find(p, start, pred_ud_ptr, userdata, ret)\
	k_arr_find(kPtrArr, p, start, pred_ud_ptr, userdata, ret)

#define k_parr_contains(p, data, ret)\
	k_arr_contains(kPtrArr, p, data, ret)

#define k_parr_swap_data(p, newdata, newcount, olddataptr)\
	K_STMT_BEGIN{\
		kpointer __save=((kPtrArr*)(p))->data;\
		((kPtrArr*)(p))->data=data;\
		((kPtrArr*)(p))->count=newcount;\
		((kPtrArr*)(p))->capa=newcount;\
		if (*(olddataptr)) *(olddataptr)=__save;\
	}K_STMT_END

#define k_parr_copy(p, o)\
	k_arr_copy(kPtrArr, p, o)

#define k_parr_foreach(p,func_ud_ptr,userdata)\
	K_STMT_BEGIN{\
		kssize_t __i, __cnt=((kPtrArr*)(p))->count;\
		for (__i=0; __i<__cnt; __i++)\
			func(userdata, k_arr_nth(p,__i));\
	}K_STMT_END

#define k_parr_loopeach(p,func_ptr)\
	K_STMT_BEGIN{\
		kssize_t __i, __cnt=((kPtrArr*)(p))->count;\
		for (__i=0; __i<__cnt; __i++)\
			func_ptr(k_arr_nth(p,__i));\
	}K_STMT_END


//////////////////////////////////////////////////////////////////////////
// container
typedef struct kCtnr
{
	kbyte*				data;
	ksize_t				count;
} kCtnr;

#define K_CTNR_DECL(name,type)\
	typedef type name##Type;\
	typedef struct name { type* data; ksize_t count; } name

#if _SB_DEBUG_
#define k_ctnr_at_safe(p,n)				(((p)->data)[((ksize_t)(n)<(p)->count) ? (ksize_t)(n) : k_mesg_assert(#n, "overflow", __FILE__, __LINE__)])
#else
#define k_ctnr_at_safe(p,n)				(((p)->data)[(ksize_t)(n)])
#endif
#define k_ctnr_nth(p,n)					(((p)->data)[(ksize_t)(n)])
#define k_ctnr_count(p)					((p)->count)
#define k_ctnr_data(p)					((p)->data)
#define k_ctnr_size(name)				(sizeof(name##Type))
#define k_ctnr_set(p,n,i)				(((p)->data)[(ksize_t)(n)]=(i))
#define k_ctnr_is_empty(p)				((p)->count==0)
#define k_ctnr_is_have(p)				((p)->count!=0)

#define k_ctnr_init(name, p, cnt)\
	K_STMT_BEGIN{\
		if ((ksize_t)(cnt)>0)\
		{\
			(p)->data=k_new((ksize_t)(cnt), name##Type);\
			(p)->count=(ksize_t)(cnt);\
		}\
		else\
		{\
			(p)->data=NULL;\
			(p)->count=0;\
		}\
	}K_STMT_END

#define k_ctnr_init_zero(name, p, cnt)\
	K_STMT_BEGIN{\
		if ((ksize_t)(cnt)>0)\
		{\
			(p)->data=k_new_zero((ksize_t)(cnt), name##Type);\
			(p)->count=(ksize_t)(cnt);\
		}\
		else\
		{\
			(p)->data=NULL;\
			(p)->count=0;\
		}\
	}K_STMT_END

#define k_ctnr_disp(name, p)\
	k_delete((kpointer)(p)->data)

#define k_ctnr_reset(name, p)\
	K_STMT_BEGIN{ (p)->count=0; }K_STMT_END

#define k_ctnr_resize(name, p, cnt)\
	k_ctnr_set_count(name, p, cnt)

#define k_ctnr_expand(name, p, cnt)\
	k_ctnr_set_count(name, p, cnt)

#define k_ctnr_set_count(name, p, cnt)\
	K_STMT_BEGIN{\
		if ((p)->count!=(ksize_t)(cnt))\
		{\
			(p)->data=k_renew((p)->data, (ksize_t)(cnt), name##Type);\
			(p)->count=(ksize_t)(cnt);\
		}\
	}K_STMT_END

#define k_ctnr_add_count(name, p, cnt)\
	K_STMT_BEGIN{\
		if ((ksize_t)(cnt)!=0)\
		{\
			(p)->data=k_renew((p)->data, (p)->count+(ksize_t)(cnt), name##Type);\
			(p)->count+=(ksize_t)(cnt);\
		}\
	}K_STMT_END

#define k_ctnr_add(name,p,v)\
	K_STMT_BEGIN{\
		k_ctnr_add_count(name,p,1);\
		k_ctnr_nth(p,(p)->count-1)=(v);\
	}K_STMT_END

#define k_ctnr_zero(name, p)\
	memset((p)->data, 0, (p)->count*sizeof(name##Type))

#define k_ctnr_contains(name,p,item,ret)\
	K_STMT_BEGIN{\
		ksize_t __i, __cnt=(p)->count;\
		for (*(ret)=-1, __i=0; __i<__cnt; __i++)\
		{\
			if (k_ctnr_nth(p,__i)==item)\
			{\
				*(ret)=(kint)__i;\
				break;\
			}\
		}\
	}K_STMT_END

#define k_ctnr_foreach(name,p,func,userdata)\
	K_STMT_BEGIN{\
		ksize_t __i, __cnt=(p)->count;\
		for (__i=0; __i<__cnt; __i++)\
			func(userdata, k_ctnr_nth(p, __i));\
	}K_STMT_END

#define k_ctnr_loopeach(name,p,func)\
	K_STMT_BEGIN{\
		ksize_t __i, __cnt=(p)->count;\
		for (__i=0; __i<__cnt; __i++)\
			func(k_ctnr_nth(p, __i));\
	}K_STMT_END

#define k_ctnr_ptr_foreach(name,p,func,userdata)\
	K_STMT_BEGIN{\
		ksize_t __i, __cnt=(p)->count;\
		for (__i=0; __i<__cnt; __i++)\
			func(userdata, &k_ctnr_nth(p, __i));\
	}K_STMT_END

#define k_ctnr_ptr_loopeach(name,p,func)\
	K_STMT_BEGIN{\
		ksize_t __i, __cnt=(p)->count;\
		for (__i=0; __i<__cnt; __i++)\
			func(&k_ctnr_nth(p, __i));\
	}K_STMT_END


//////////////////////////////////////////////////////////////////////////
// pointer container 
K_CTNR_DECL(kPtrCtnr, kpointer);

#define k_pctnr_at_safe(p,n)			k_ctnr_at_safe(p,n)
#define k_pctnr_nth(p,n)				k_ctnr_nth(p,n)
#define k_pctnr_count(p,n)				k_ctnr_count(p,n)
#define k_pctnr_data(p)					k_ctnr_data(p)

#define k_pctnr_init(p, count)\
	k_ctnr_init(kPtrCtnr, (kPtrCtnr*)p, count)

#define k_pctnr_initZero(p, count)\
	k_ctnr_initZero(kPtrCtnr, (kPtrCtnr*)p, count)

#define k_pctnr_disp(p)\
	k_ctnr_disp(kPtrCtnr, (kPtrCtnr*)p)

#define k_pctnr_set_count(p, count)\
	k_ctnr_set_count(kPtrCtnr, (kPtrCtnr*)p, count)

#define k_pctnr_add_count(p, count)\
	k_ctnr_add_count(kPtrCtnr, (kPtrCtnr*)p, count)

#define k_pctnr_add(p, item)\
	k_ctnr_add(kPtrCtnr, (kPtrCtnr*)p, (kpointer)item)

#define k_pctnr_zero(p)\
	k_ctnr_zero(kPtrCtnr, (kPtrCtnr*)p)

#define k_pctnr_foreach(p, func, userdata)\
	k_ctnr_foreach(kPtrCtnr, (kPtrCtnr*)p, func, userdata)

#define k_pctnr_loopeach(p, func)\
	k_ctnr_loopeach(kPtrCtnr, (kPtrCtnr*)p, func)


//////////////////////////////////////////////////////////////////////////
// common array & container
K_ARR_DECL(kByteArr, kbyte);
K_ARR_DECL(kIntArr, kint);
K_ARR_DECL(kUintArr, kuint);
K_ARR_DECL(kPcharArr, char*)						// kPtrArr
K_ARR_DECL(kPccharArr, const char*);				// kPtrArr
K_ARR_DECL(kAnyCbArr, kanycb);

K_CTNR_DECL(kByteCtn, kbyte);
K_CTNR_DECL(kIntCtn, kint);
K_CTNR_DECL(kUintCtn, kuint);
K_CTNR_DECL(kPcharCtn, char*);						// kPtrCtnr
K_CTNR_DECL(kPccharCtn, const char*);				// kPtrCtnr
K_CTNR_DECL(kAnyCbCtn, kanycb);


//////////////////////////////////////////////////////////////////////////
// list
typedef struct kListNode
{
	struct kListNode*	next;
	struct kListNode*	prev;
	kbyte				data[];
} kListNode;

typedef struct kList
{
	kListNode*			frst;
	kListNode*			last;
	kssize_t			count;
} kList;

#define K_LIST_DECL(name,type)\
	typedef struct name name;\
	typedef type name##Type;\
	struct name##Node { struct name##Node *next, *prev; type data; };\
	struct name { struct name##Node *frst, *last; kssize_t count; }

#define k_list_count(p)						((p)->count)
#define k_list_node_first(p)				((p)->last)
#define k_list_node_last(p)					((p)->frst)
#define k_list_data_first(p)				((p)->last->data)
#define k_list_data_last(p)					((p)->frst->data)
#define k_list_is_have(p)					((p)->count!=0)
#define k_list_is_empty(p)					((p)->count==0)

#define k_list_init(name,p)\
	K_STMT_BEGIN{\
		(p)->frst=NULL;\
		(p)->last=NULL;\
		(p)->count=0;\
	}K_STMT_END

#define k_list_disp(name,p)\
	K_STMT_BEGIN{\
		struct name##Node *__node, *__next;\
		for (__node=(p)->frst; __node; __node=__next)\
		{\
			__next=__node->next;\
			k_delete(__node);\
		}\
	}K_STMT_END

#define k_list_clear(name,p)\
	K_STMT_BEGIN{\
		k_list_disp(name,p);\
		(p)->frst=(p)->last=NULL;\
		(p)->count=0;\
	}K_STMT_END

#define k_list_remove_node(name,p,node)\
	K_STMT_BEGIN{\
		struct name##Node* __node=(node);\
		if (__node)\
		{\
			if (__node->next)\
				__node->next->prev=__node->prev;\
			else\
			{\
				k_assert_eq((p)->last, __node);\
				(p)->last=__node->prev;\
			}\
			if (__node->prev)\
				__node->prev->next=__node->next;\
			else\
			{\
				k_assert_eq((p)->frst, __node);\
				(p)->frst=__node->next;\
			}\
			(p)->count--;\
			k_delete(__node);\
		}\
	}K_STMT_END

#define k_list_remove_first(name,p)\
	k_list_remove_node(name, p, (p)->last)

#define k_list_remove_last(name,p)\
	k_list_remove_node(name, p, (p)->frst)

// value type
#define k_list_disp_cb(name,p,func_user_data,userdata)\
	K_STMT_BEGIN{\
		struct name##Node *__node, *__next;\
		for (__node=(p)->frst; __node; __node=__next)\
		{\
			__next=__node->next;\
			func_user_data(userdata,__node->data);\
			k_delete(__node);\
		}\
	}K_STMT_END

#define k_list_append(name,p,item)\
	K_STMT_BEGIN{\
		struct name##Node* __node=k_new_1(struct name##Node);\
		__node->data=item;\
		if ((p)->frst)\
			(p)->frst->prev=__node;\
		else\
			(p)->last=__node;\
		__node->next=(p)->frst;\
		__node->prev=NULL;\
		(p)->frst=__node;\
		(p)->count++;\
	}K_STMT_END

#define k_list_prepend(name,p,item)\
	K_STMT_BEGIN{\
		struct name##Node* __node=k_new_1(struct name##Node);\
		__node->data=item;\
		if ((p)->last)\
			(p)->last->next=__node;\
		else\
			(p)->frst=__node;\
		__node->prev=(p)->last;\
		__node->next=NULL;\
		(p)->last=__node;\
		(p)->count++;\
	}K_STMT_END

#define k_list_remove(name,p,item)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		for (__node=(p)->frst; __node; __node=__node->next)\
		{\
			if (__node->data==(item))\
			{\
				k_list_remove_node(name, p, __node);\
				break;\
			}\
		}\
	}K_STMT_END

#define k_list_remove_cmp(name,p,func_data_item,item)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		for (__node=(p)->frst; __node; __node=__node->next)\
		{\
			if (func_data_pitem(__node->data, item))\
			{\
				k_list_remove_node(name, p, __node);\
				break;\
			}\
		}\
	}K_STMT_END

#define k_list_contains(name,p,item,retnode)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		for (*(retnode)=NULL, __node=(p)->frst; __node; __node=__node->next)\
		{\
			if (__node->data==(item))\
			{\
				*(retnode)=__node;\
				break;\
			}\
		}\
	}K_STMT_END

#define k_list_find(name,p,predicate_user_data,userdata,retnode)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		for (*(retnode)=NULL, __node=(p)->frst; __node; __node=__node->next)\
		{\
			if (predicate_user_data(userdata, __node->data))\
			{\
				*(retnode)=__node;\
				break;\
			}\
		}\
	}K_STMT_END

#define k_list_foreach(name,p,func_user_data,userdata)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		for (__node=(p)->last; __node; __node=__node->prev)\
			func_user_data(userdata, __node->data);\
	}K_STMT_END

#define k_list_loopeach(name,p,func_data)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		for (__node=(p)->last; __node; __node=__node->prev)\
			func_data(__node->data);\
	}K_STMT_END

// reference type
#define k_list_ref_disp_cb(name,p,func_user_pdata,userdata)\
	K_STMT_BEGIN{\
		struct name##Node *__node, *__next;\
		for (__node=(p)->frst; __node; __node=__next)\
		{\
			__next=__node->next;\
			func_user_pdata(userdata,&__node->data);\
			k_delete(__node);\
		}\
	}K_STMT_END

#define k_list_ref_append(name,p,pitem)\
	K_STMT_BEGIN{\
		struct name##Node* __node=k_new_1(struct name##Node);\
		memcpy(&__node->data, pitem, sizeof(name##Type));\
		if ((p)->frst)\
			(p)->frst->prev=__node;\
		else\
			(p)->last=__node;\
		__node->next=(p)->frst;\
		__node->prev=NULL;\
		(p)->frst=__node;\
		(p)->count++;\
	}K_STMT_END

#define k_list_ref_prepend(name,p,pitem)\
	K_STMT_BEGIN{\
		struct name##Node* __node=k_new_1(struct name##Node);\
		memcpy(&__node->data, pitem, sizeof(name##Type));\
		if ((p)->last)\
			(p)->last->next=__node;\
		else\
			(p)->frst=__node;\
		__node->prev=(p)->last;\
		__node->next=NULL;\
		(p)->last=__node;\
		(p)->count++;\
	}K_STMT_END

#define k_list_ref_remove(name,p,pitem)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		for (__node=(p)->frst; __node; __node=__node->next)\
		{\
			if (memcmp(&__node->data, pitem)==0)\
			{\
				k_list_remove_node(name, p, __node);\
				break;\
			}\
		}\
	}K_STMT_END

#define k_list_ref_remove_cmp(name,p,func_pdata_pitem,pitem)\
	K_STMT_BEGIN{\
		struct name##Node* __rcnode;\
		for (__rcnode=(p)->frst; __rcnode; __rcnode=__rcnode->next)\
		{\
			if (func_pdata_pitem(&__rcnode->data, pitem))\
			{\
				k_list_remove_node(name, p, __rcnode);\
				break;\
			}\
		}\
	}K_STMT_END

#define k_list_ref_contains(name,p,pitem,retnode)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		for (*(retnode)=NULL, __node=(p)->frst; __node; __node=__node->next)\
		{\
			if (memcmp(&__node->data, pitem)==0)\
			{\
				*(retnode)=__node;\
				break;\
			}\
		}\
	}K_STMT_END

#define k_list_ref_find(name,p,predicate_user_pdata,userdata,retnode)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		for (*(retnode)=NULL, __node=(p)->frst; __node; __node=__node->next)\
		{\
			if (predicate_user_pdata(userdata, &__node->data))\
			{\
				*(retnode)=__node;\
				break;\
			}\
		}\
	}K_STMT_END

#define k_list_ref_foreach(name,p,func_user_pdata,userdata)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		for (__node=(p)->last; __node; __node=__node->prev)\
			func_user_pdata(userdata, &__node->data);\
	}K_STMT_END

#define k_list_ref_loopeach(name,p,func_pdata)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		for (__node=(p)->last; __node; __node=__node->prev)\
			func_pdata(&__node->data);\
	}K_STMT_END


//////////////////////////////////////////////////////////////////////////
// node list
typedef struct kNlNode
{
	struct kNlNode*		next;
	struct kNlNode*		prev;
} kNlNode;

typedef struct kNodeList
{
	kNlNode*			frst;
	kNlNode*			last;
	ksize_t				count;
} kNodeList;

#define K_NODELIST_DECL(name,type)\
	typedef struct name name;\
	typedef type name##Type;\
	struct name { type* frst; type* last; ksize_t count; }

#define k_nodelist_count(p)				((p)->count)
#define k_nodelist_first(p)				((p)->last)
#define k_nodelist_last(p)				((p)->frst)
#define k_nodelist_is_have(p)			((p)->count!=0)
#define k_nodelist_is_empty(p)			((p)->count==0)

#define k_nodelist_init(name,p)\
	K_STMT_BEGIN{\
		(p)->frst=NULL;\
		(p)->last=NULL;\
		(p)->count=0;\
	}K_STMT_END

#define k_nodelist_disp(name,p)\
	K_STMT_BEGIN{\
		name##Type *__node, *__next;\
		for (__node=(p)->frst; __node; __node=__next)\
		{\
			__next=__node->next;\
			k_delete(__node);\
		}\
	}K_STMT_END

#define k_nodelist_disp_cb(name,p,func1)\
	K_STMT_BEGIN{\
		name##Type *__node, *__next;\
		for (__node=(p)->frst; __node; __node=__next)\
		{\
			__next=__node->next;\
			func1(__node);\
		}\
	}K_STMT_END

#define k_nodelist_append(name,p,item)\
	K_STMT_BEGIN{\
		if ((p)->frst)\
			(p)->frst->prev=(item);\
		else\
			(p)->last=(item);\
		(item)->next=(p)->frst;\
		(item)->prev=NULL;\
		(p)->frst=(item);\
		(p)->count++;\
	}K_STMT_END

#define k_nodelist_prepend(name,p,item)\
	K_STMT_BEGIN{\
		if ((p)->last)\
			(p)->last->next=(item);\
		else\
			(p)->frst=(item);\
		(item)->prev=(p)->last;\
		(item)->next=NULL;\
		(p)->last=(item);\
		(p)->count++;\
	}K_STMT_END

#define k_nodelist_clear(name,p)\
	K_STMT_BEGIN{\
		k_nodelist_disp(name,p);\
		(p)->frst=(p)->last=NULL;\
		(p)->count=0;\
	}K_STMT_END

#define k_nodelist_clear_cb(name,p,func_1)\
	K_STMT_BEGIN{\
		k_nodelist_disp_cb(name,p,func_1);\
		(p)->frst=(p)->last=NULL;\
		(p)->count=0;\
	}K_STMT_END

#define k_nodelist_remove(name,p,item,func_1)\
	K_STMT_BEGIN{\
		if (item!=NULL)\
		{\
			name##Type* __node=(name##Type*)(item);\
			if (__node->next)\
				__node->next->prev=__node->prev;\
			else\
			{\
				k_assert_eq((p)->last, __node);\
				(p)->last=__node->prev;\
			}\
			if (__node->prev)\
				__node->prev->next=__node->next;\
			else\
			{\
				k_assert_eq((p)->frst, __node);\
				(p)->frst=__node->next;\
			}\
			(p)->count--;\
			func_1(__node);\
		}\
	}K_STMT_END

#define k_nodelist_remove_first(name,p,func_1)\
	k_nodelist_remove(name, (p)->last,func_1)

#define k_nodelist_remove_last(name,p,func_1)\
	k_nodelist_remove(name, (p)->frst,func_1)

#define k_nodelist_unlink(name,p,item)\
	K_STMT_BEGIN{\
		if (item!=NULL)\
		{\
			name##Type* __node=(name##Type*)(item);\
			if (__node->next)\
				__node->next->prev=__node->prev;\
			else\
			{\
				k_assert_eq((p)->last, __node);\
				(p)->last=__node->prev;\
			}\
			if (__node->prev)\
				__node->prev->next=__node->next;\
			else\
			{\
				k_assert_eq((p)->frst, __node);\
				(p)->frst=__node->next;\
			}\
			(p)->count--;\
			__node->prev=__node->next=NULL;\
		}\
	}K_STMT_END

#define k_nodelist_contains(name,p,item,retcham)\
	K_STMT_BEGIN{\
		name##Type* __node;\
		for (*(retcham)=FALSE, __node=(p)->frst; __node; __node=__node->next)\
		{\
			if (__node==(item))\
			{\
				*(retcham)=TRUE;\
				break;\
			}\
		}\
	}K_STMT_END

#define k_nodelist_find(name,p,predicate_user_node,userdata,retcham)\
	K_STMT_BEGIN{\
		name##Type* __node;\
		for (*(retcham)=FALSE, __node=(p)->last; __node; __node=__node->prev)\
		{\
			if (predicate_user_node(userdata,__node))\
			{\
				*(retcham)=TRUE;\
				break;\
			}\
		}\
	}K_STMT_END

#define k_nodelist_foreach(name,p,func_user_node,userdata)\
	K_STMT_BEGIN{\
		name##Type* __node;\
		for (__node=(p)->last; __node; __node=__node->prev)\
			func_user_node(userdata,__node);\
	}K_STMT_END

#define k_nodelist_loopeach(name,p,func_node)\
	K_STMT_BEGIN{\
		name##Type* __node;\
		for (__node=(p)->last; __node; __node=__node->prev)\
			func_node(__node);\
	}K_STMT_END


//////////////////////////////////////////////////////////////////////////
// pointer list
K_LIST_DECL(kPtrList, kpointer);

#define k_plist_count(p)				k_list_count(p)
#define k_plist_first(p)				k_list_data_first(p)
#define k_plist_last(p)					k_list_data_last(p)
#define k_plist_peek_first(p)			k_list_node_first(p)
#define k_plist_peek_last(p)			k_list_node_last(p)
#define k_plist_is_have(p)				k_list_is_have(p)
#define k_plist_is_empty(p)				k_list_is_empty(p)

#define k_plist_init(p)\
	k_list_init(kPtrList, p)

#define k_plist_disp(p)\
	k_list_disp(kPtrList, p)

#define k_plist_disp_cb(p,func_user_data,userdata)\
	k_list_disp_cb(kPtrList, p, func_user_data, userdata)

#define k_plist_append(p,item)\
	k_list_append(kPtrList, p, item)

#define k_plist_prepend(p,item)\
	k_list_prepend(kPtrList, p, item)

#define k_plist_clear(p)\
	k_list_clear(kPtrList, p)

#define k_plist_remove(p,item)\
	k_list_remove(kPtrList, p, item)

#define k_plist_remove_first(p)\
	k_list_remove_first(kPtrList, p)

#define k_plist_remove_last(p)\
	k_list_remove_last(kPtrList, p)

K_INLINE kcham k_plist_contains(kPtrList* p, kpointer item)
{
	struct kPtrListNode* node;
	k_list_contains(kPtrList, p, item, &node);
	return node!=NULL;
}

K_INLINE kcham k_plist_find(kPtrList* p, kcham (*pred)(kpointer, kpointer), kpointer userdata)
{
	struct kPtrListNode* node;
	k_list_find(kPtrList, p, pred, userdata, &node);
	return node!=NULL;
}

#define k_plist_foreach(p,func_user_data,userdata)\
	k_list_foreach(kPtrList, p, func_user_data, userdata)

#define k_plist_loopeach(p,func_data)\
	k_list_loopeach(kPtrList, p, func_data)


//////////////////////////////////////////////////////////////////////////
// solo list
typedef struct kSlist
{
	struct kSlist*		next;
	kbyte				data[];
} kSlist;

#define K_SLIST_DECL(name,type)\
	typedef type name##Type;\
	typedef struct name { struct name* next; type data; } name;

#define k_slist_last(p)\
	k_slist_inl_last(p)

#define k_slist_nth(p,nth)\
	k_slist_inl_nth(p, nth)

#define k_slist_data(p,nth)\
	(((kSlist*)k_slist_inl_nth(p, nth))->data)

#define k_slist_count(p)\
	k_slist_inl_count(p)

#define k_slist_delete(name, p, ptrptr)\
	K_STMT_BEGIN{\
		if ((p)==NULL)\
			*(ptrptr)=NULL;\
		else\
		{\
			name* __n=(p)->next;\
			k_delete(p);\
			*(ptrptr)=__n;\
		}\
	}K_STMT_END

#define k_slist_disp(name, p)\
	K_STMT_BEGIN{\
		name* __n;\
		name* __p;\
		for (__p=(p); __p; __p=__n)\
		{\
			__n=__p->next;\
			k_delete(__p);\
		}\
	}K_STMT_END

#define k_slist_disp_func(name, p, func_1)\
	K_STMT_BEGIN{\
		name* __n;\
		name* __p;\
		for (__p=(p); __p; __p=__n)\
		{\
			__n=__p->next;\
			func_1(__p);\
		}\
	}K_STMT_END

#define k_slist_concat(name, p1, p2, ptrptr)\
	K_STMT_BEGIN{\
		if ((p2)==NULL)\
			*(ptrptr)=(p1);\
		else\
		{\
			if ((p1)==NULL)\
				*(ptrptr)=(p2);\
			else\
			{\
				name* __l=(name*)k_slist_last(p1);\
				__l->next=(p2);\
				*(ptrptr)=(p1);\
			}\
		}\
	}K_STMT_END

#define k_slist_append(name, p, item, ptrptr)\
	K_STMT_BEGIN{\
		name* __np;\
		__np=k_new_1(name);\
		__np->next=NULL;\
		__np->data=item;\
		if ((p)==NULL)\
			*(ptrptr)=__np;\
		else\
		{\
			name* __l=(name*)k_slist_last(p);\
			__l->next=__np;\
			*(ptrptr)=(p);\
		}\
	}K_STMT_END

#define k_slist_prepend(name, p, item, ptrptr)\
	K_STMT_BEGIN{\
		name* __np;\
		__np=k_new_1(name);\
		__np->next=(p);\
		__np->data=item;\
		*(ptrptr)=__np;\
	}K_STMT_END

#define k_slist_reserve_append(name, p, ptrptr)\
	K_STMT_BEGIN{\
		name* __np;\
		__np=k_new_0(name);\
		if ((p)==NULL)\
			*(ptrptr)=__np;\
		else\
		{\
			name* __l=(name*)k_slist_last(p);\
			__l->next=__np;\
			*(ptrptr)=(p);\
		}\
	}K_STMT_END

#define k_slist_reserve_prepend(name, p, ptrptr)\
	K_STMT_BEGIN{\
		name* __np;\
		__np=k_new_0(name);\
		__np->next=(p);\
		*(ptrptr)=__np;\
	}K_STMT_END

#define k_slist_insert(name, p, sib, item, ptrptr)\
	K_STMT_BEGIN{\
		if ((p)==NULL)\
		{\
			name* __np=k_new_0(name);\
			__np->next=NULL;\
			__np->data=item;\
			*(ptrptr)=__np;\
		}\
		else\
		{\
			name* __l=NULL;\
			name* __np;\
			for (__np=(p); __np; __l=__np, __np=__l->next)\
			{\
				if (__np==(sib))\
					break;\
			}\
			__np=k_new_1(name);\
			__np->data=item;\
			if (__l==NULL)\
			{\
				__np->next=(p);\
				*(ptrptr)=__np;\
			}\
			else\
			{\
				__np->next=__l->next;\
				__l->next=__np;\
				*(ptrptr)=(p);\
			}\
		}\
	}K_STMT_END

#define k_slist_insert_nth(name, p, nth, item, ptrptr)\
	K_STMT_BEGIN{\
		kint __h=nth;\
		if (__h<0)\
		{\
			k_slist_append(name, p, item, ptrptr);\
		}\
		else if (__h==0)\
		{\
			k_slist_prepend(name, p, item, ptrptr);\
		}\
		else\
		{\
			name* __np=k_new_1(name);\
			__np->data=item;\
			if (p==NULL)\
			{\
				__np->next=NULL;\
				*(ptrptr)=__np;\
			}\
			else\
			{\
				name* __t=(p);\
				name* __v=NULL;\
				while (__h-->0 && __t)\
				{\
					__v=__t;\
					__t=__t->next;\
				}\
				if (__v)\
				{\
					__np->next=__v->next;\
					__v->next=__np;\
					*(ptrptr)=(p);\
				}\
				else\
				{\
					__np->next=(p);\
					*(ptrptr)=__np;\
				}\
			}\
		}\
	}K_STMT_END

#define k_slist_remove(name, p, item, ptrptr)\
	K_STMT_BEGIN{\
		name* __r=(p);\
		name* __t=(p);\
		name* __v=NULL;\
		while (__t)\
		{\
			if (__t->data==item)\
			{\
				if (__v)\
					__v->next=__t->next;\
				else\
					__r=__t->next;\
				k_delete(__t);\
				break;\
			}\
			__v=__t;\
			__t=__t->next;\
		}\
		*(ptrptr)=__r;\
	}K_STMT_END

#define k_slist_remove_link(name, p, link, ptrptr)\
	K_STMT_BEGIN{\
		name* __r=(p);\
		name* __t=(p);\
		name* __v=NULL;\
		while (__t)\
		{\
			if (__t==(link))\
			{\
				if (__v)\
					__v->next=__t->next;\
				if (__r==__t)\
					__r=__r->next;\
				__t->next=NULL;\
				break;\
			}\
			__v=__t;\
			__t=__t->next;\
		}\
		k_delete(link);\
		*(ptrptr)=__r;\
	}K_STMT_END

#define k_slist_copy(name, p, ptrptr)\
	K_STMT_BEGIN{\
		if ((p)==NULL)\
			*(ptrptr)=NULL;\
		else\
		{\
			name* __p;\
			name* __n;\
			name* __l;\
			__n=k_new_0(name);\
			__n->data=(p)->data;\
			__l=__n;\
			__p=(p)->next;\
			while (__p)\
			{\
				__l->next=k_new_1(name);\
				__l=__l->next;\
				__l->data=__p->data;\
				__p=__p->next;\
			}\
			__l->next=NULL;\
			*(ptrptr)=__n;\
		}\
	}K_STMT_END

#define k_slist_contains(name,p,item,ptrptr)\
	K_STMT_BEGIN{\
		name* __p=(p);\
		while (__p)\
		{\
			if (__p->data==item)\
				break;\
			__p=__p->next;\
		}\
		*(ptrptr)=__p;\
	}K_STMT_END

#define k_slist_contains_func(name,p,func2,item,ptrptr)\
	K_STMT_BEGIN{\
		name* __p=(p);\
		while (__p)\
		{\
			if (func2(__p->data, item))\
				break;\
			__p=__p->next;\
		}\
		*(ptrptr)=__p;\
	}K_STMT_END

#define k_slist_foreach(name,p,func_2,userdata)\
	K_STMT_BEGIN{\
		name* __p=(p);\
		while (__p)\
		{\
			name* __n=__p->next;\
			func_2(userdata, __p->data);\
			__p=__n;\
		}\
	}K_STMT_END

#define k_slist_loopeach(name,p,func_1)\
	K_STMT_BEGIN{\
		name* __p=(p);\
		while (__p)\
		{\
			name* __n=__p->next;\
			func_1(__p->data);\
			__p=__n;\
		}\
	}K_STMT_END

K_INLINE kpointer k_slist_inl_last(kpointer ptr)
{
	kSlist* p=(kSlist*)ptr;
	if (p)
	{
		while (p->next)
			p=p->next;
	}
	return p;
}

K_INLINE kpointer k_slist_inl_nth(kpointer ptr, ksize_t nth)
{
	kSlist* p=(kSlist*)ptr;
	while (nth-->0 && p)
		p=p->next;
	return (kpointer)p;
}

K_INLINE ksize_t k_slist_inl_count(kpointer ptr)
{
	kSlist* p=(kSlist*)ptr;
	ksize_t n=0;
	while (p)
	{
		n++;
		p=p->next;
	}
	return n;
}


//////////////////////////////////////////////////////////////////////////
// pointer solo list
K_SLIST_DECL(kPtrSlist, kpointer);

#define k_pslist_last(p)\
	k_slist_last(p)
	
#define k_pslist_nth(p, nth)\
	k_slist_nth(p, nth)
	
#define k_pslist_data(p, nth)\
	k_slist_data(p, nth)
	
#define k_pslist_count(p)\
	k_slist_count(p)

K_INLINE kPtrSlist* k_pslist_delete(kPtrSlist* p)
{
	k_slist_delete(kPtrSlist, p, &p);
	return p;
}

K_INLINE void k_pslist_disp(kPtrSlist* p, void (*func_1)(kpointer))
{
	if (!func_1)
	{
		k_slist_disp(kPtrSlist, p);
	}
	else
	{
		kPtrSlist* n;
		for (; p; p=n)
		{
			n=p->next;
			if (func_1)
				func_1(p->data);
			k_delete(p);
		}
	}
}

K_INLINE kPtrSlist* k_pslist_concat(kPtrSlist* p1, kPtrSlist* p2)
{
	k_slist_concat(kPtrSlist, p1, p2, &p1);
	return p1;
}

K_INLINE kPtrSlist* k_pslist_append(kPtrSlist* p, kpointer item)
{
	k_slist_append(kPtrSlist, p, item, &p);
	return p;
}

K_INLINE kPtrSlist* k_pslist_prepend(kPtrSlist* p, kpointer item)
{
	k_slist_prepend(kPtrSlist, p, item, &p);
	return p;
}

K_INLINE kPtrSlist* k_pslist_insert(kPtrSlist* p, kPtrSlist* sib, kpointer item)
{
	k_slist_insert(kPtrSlist, p, sib, item, &p);
	return p;
}

K_INLINE kPtrSlist* k_pslist_insert_nth(kPtrSlist* p, kint nth, kpointer item)
{
	k_slist_insert_nth(kPtrSlist, p, nth, item, &p);
	return p;
}

K_INLINE kPtrSlist* k_pslist_remove(kPtrSlist* p, kpointer item)
{
	k_slist_remove(kPtrSlist, p, item, &p);
	return p;
}

K_INLINE kPtrSlist* k_pslist_remove_link(kPtrSlist* p, kPtrSlist* link)
{
	k_slist_remove_link(kPtrSlist, p, link, &p);
	return p;
}

K_INLINE kPtrSlist* k_pslist_copy(kPtrSlist* p)
{
	kPtrSlist* n;
	k_slist_copy(kPtrSlist, p, &n);
	return n;
}

K_INLINE kPtrSlist* k_pslist_contains(kPtrSlist* p, kpointer item)
{
	k_slist_contains(kPtrSlist, p, item, &p);
	return p;
}

#define k_pslist_foreach(p,func_2,userdata)\
	k_slist_foreach(kPtrSlist, p, func_2, userdata)

#define k_pslist_loopeach(p,func_1)\
	k_slist_LoopEach(kPtrSlist, p, func_1);


//////////////////////////////////////////////////////////////////////////
// fixed slice
typedef struct kSlice
{
	kbyte*				data;
	ksize_t				max;
	ksize_t				count;
} kSlice;

#define K_SLICE_DECL(name, type)\
	typedef type name##Type;\
	typedef struct name { type* data; ksize_t max; ksize_t count; } name

#define k_slice_nth(p,n)				(((p)->data)[(ksize_t)(n)])
#define k_slice_invat(p,n)				(((p)->data)[((p)->count-1-(ksize_t)(n)])
#define k_slice_count(p)				((p)->count)
#define k_slice_maximum(p)				((p)->max)
#define k_slice_data(p)					((p)->data)
#define k_slice_sizeof(name)			(sizeof(name##Type))
#define k_slice_is_empty(p)				((p)->count==0)
#define k_slice_is_have(p)				((p)->count!=0)

#define k_slice_test_init(name,p,_max)\
	K_STMT_BEGIN{\
		k_assert((p)->data==NULL && (p)->max==0 && (p)->count==0, "uninitialized slice memory.");\
		(p)->data=k_new(_max, name##Type);\
		(p)->max=_max;\
	}K_STMT_END

#define k_slice_init(name,p,_max)\
	K_STMT_BEGIN{\
		(p)->max=_max;\
		(p)->count=0;\
		(p)->data=k_new((p)->max, name##Type);\
	}K_STMT_END

#define k_slice_disp(name,p)\
	K_STMT_BEGIN{ k_delete((p)->data); }K_STMT_END

#define k_slice_clear(name,p)\
	K_STMT_BEGIN{ (p)->count=0; }K_STMT_END

#define k_slice_disable(name,p)\
	K_STMT_BEGIN{ (p)->max=(p)->count; }K_STMT_END

#define k_slice_expand(name,p,newmax)\
	K_STMT_BEGIN{\
		if ((p)->count>(newmax))\
			(p)->count=(newmax);\
		(p)->data=k_renew((p)->data, newmax, name##Type);\
		(p)->max=(newmax);\
	}K_STMT_END

#define k_slice_push(name,p,itemref,retchamref)\
	K_STMT_BEGIN{\
		kcham* __r=(retchamref);\
		if ((p)->count==(p)->max)\
		{\
			if (__r) *__r=FALSE;\
		}\
		else\
		{\
			if (__r) *__r=TRUE;\
			(p)->data[(p)->count]=*(itemref);\
			(p)->count++;\
		}\
	}K_STMT_END

#define k_slice_pop(name,p,retchamref)\
	K_STMT_BEGIN{\
		kcham* __r=(retchamref);\
		if ((p)->count==0)\
		{\
			if (__r) *__r=FALSE;\
		}\
		else if ((p)->count==1)\
		{\
			if (__r) *__r=TRUE;\
			(p)->count=0;\
		}\
		else\
		{\
			if (__r) *__r=TRUE;\
			(p)->count--;\
			(p)->data[0]=(p)->data[(p)->count];\
		}\
	}K_STMT_END

#define k_slice_pop_value(name,p,retvalueref,retchamref)\
	K_STMT_BEGIN{\
		kcham* __r=(retchamref);\
		if ((p)->count==0)\
		{\
			if (__r) *__r=FALSE;\
		}\
		else if ((p)->count==1)\
		{\
			if (__r) *__r=TRUE;\
			*(retvalueref)=(p)->data[0];\
			(p)->count=0;\
		}\
		else\
		{\
			if (__r) *__r=TRUE;\
			*(retvalueref)=(p)->data[0];\
			(p)->count--;\
			(p)->data[0]=(p)->data[(p)->count];\
		}\
	}K_STMT_END

#define k_slice_find(name,p,start,func2,userdata,retintref)\
	K_STMT_BEGIN{\
		ksize_t __i, __cnt=(p)->count;\
		for (*(retintref)=-1, __i=(ksize_t)(start); __i<__cnt; __i++)\
		{\
			if (func2(userdata, &k_slice_nth(p,__i)))\
			{\
				*(retintref)=(kint)__i;\
				break;\
			}\
		}\
	}K_STMT_END

#define k_slice_contains(name,p,itemptr,retintref)\
	K_STMT_BEGIN{\
		ksize_t __i, __cnt=(p)->count;\
		for (*(retintref)=-1, __i=0; __i<__cnt; __i++)\
		{\
			if (memcmp(&k_slice_nth(p,__i), itemptr, sizeof(name##Type))==0)\
			{\
				*(retintref)=(kint)__i;\
				break;\
			}\
		}\
	}K_STMT_END

#define k_slice_contains_func(name,p,func,itemptr,retintref)\
	K_STMT_BEGIN{\
		ksize_t __i, __cnt=(p)->count;\
		for (*(retintref)=-1, __i=0; __i<__cnt; __i++)\
		{\
			if (func(&k_slice_nth(p,__i),(itemptr)))\
			{\
				*(retintref)=(kint)__i;\
				break;\
			}\
		}\
	}K_STMT_END

#define k_slice_foreach(name,p,func,userdata)\
	K_STMT_BEGIN{\
		ksize_t __i, __cnt=(p)->count;\
		for (__i=0; __i<__cnt; __i++)\
			func(userdata, &k_slice_nth(p,__i));\
	}K_STMT_END

#define k_slice_loopeach(name,p,func)\
	K_STMT_BEGIN{\
		ksize_t __i, __cnt=(p)->count;\
		for (__i=0; __i<__cnt; __i++)\
			func(&k_slice_nth(p,__i));\
	}K_STMT_END

#define k_slice_ptr_push(name,p,item,retchamref)\
	K_STMT_BEGIN{\
		kcham* __r=(retchamref);\
		if ((p)->count==(p)->max)\
		{\
			if (__r) *__r=FALSE;\
		}\
		else\
		{\
			if (__r) *__r=TRUE;\
			(p)->data[(p)->count]=(item);\
			(p)->count++;\
		}\
	}K_STMT_END

#define k_slice_ptr_pop(name,p,retchamref)\
	k_slice_Pop(name,p,retchamref)

#define k_slice_ptr_pop_value(name,p,retvalueref)\
	K_STMT_BEGIN{\
		if ((p)->count==0)\
		{\
			*(retvalueref)=NULL;\
		}\
		else if ((p)->count==1)\
		{\
			*(retvalueref)=(p)->data[0];\
			(p)->count=0;\
		}\
		else\
		{\
			*(retvalueref)=(p)->data[0];\
			(p)->count--;\
			(p)->data[0]=(p)->data[(p)->count];\
		}\
	}K_STMT_END


#define k_slice_ptr_find(name,p,start,func2,userdata,retintref)\
	K_STMT_BEGIN{\
		ksize_t __i, __cnt=(p)->count;\
		for (*(retintref)=-1, __i=(ksize_t)(start); __i<__cnt; __i++)\
		{\
			if (func2(userdata, k_slice_nth(p,__i)))\
			{\
				*(retintref)=(kint)__i;\
				break;\
			}\
		}\
	}K_STMT_END

#define k_slice_ptr_contains(name,p,item,retintref)\
	K_STMT_BEGIN{\
		ksize_t __i, __cnt=(p)->count;\
		for (*(retintref)=-1, __i=0; __i<__cnt; __i++)\
		{\
			if (k_slice_nth(p,__i)==item)\
			{\
				*(retintref)=(kint)__i;\
				break;\
			}\
		}\
	}K_STMT_END

#define k_slice_ptr_contains_func(name,p,func,item,retintref)\
	K_STMT_BEGIN{\
		ksize_t __i, __cnt=(p)->count;\
		for (*(retintref)=-1, __i=0; __i<__cnt; __i++)\
		{\
			if (func(k_slice_nth(p,__i),(item)))\
			{\
				*(retintref)=(kint)__i;\
				break;\
			}\
		}\
	}K_STMT_END

#define k_slice_ptr_foreach(name,p,func,userdata)\
	K_STMT_BEGIN{\
		ksize_t __i, __cnt=(p)->count;\
		for (__i=0; __i<__cnt; __i++)\
			func(userdata, k_slice_nth(p,__i));\
	}K_STMT_END

#define k_slice_ptr_loopeach(name,p,func)\
	K_STMT_BEGIN{\
		ksize_t __i, __cnt=(p)->count;\
		for (__i=0; __i<__cnt; __i++)\
			func(k_slice_nth(p,__i));\
	}K_STMT_END


//////////////////////////////////////////////////////////////////////////
// hash
typedef struct kHashNode
{
	struct kHashNode*	sib;
	struct kHashNode*	next;
	struct kHashNode*	prev;
	ksize_t				hash;
	kuintptr			key;
	kuintptr			value;
} kHashNode;

typedef struct kHash
{
	ksize_t				revision;
	ksize_t				bucket;
	ksize_t				count;
	struct kHashNode**	nodes;
	struct kHashNode*	frst;
	struct kHashNode*	last;
} kHash;

#define K_HASH_DECL(name,keytype,valuetype)\
	typedef keytype name##Key;\
	typedef valuetype name##Value;\
	typedef struct name##Node { struct name##Node* sib; struct name##Node* next; struct name##Node* prev; ksize_t hash; name##Key key; name##Value value; } name##Node;\
	typedef struct name { ksize_t revision; ksize_t bucket; ksize_t count; struct name##Node** nodes; struct name##Node* frst; struct name##Node* last; } name

#define K_HASH_HASH(name,func1)\
	K_INLINE ksize_t name##_Hash_Cb_Hash(name##Key* key) { return func1(key); }
#define K_HASH_HASH_PURE(name)\
	K_INLINE ksize_t name##_Hash_Cb_Hash(name##Key* key) { return K_CAST_PTR_TO_UINT(*key); }

#define K_HASH_EQ(name,func2)\
	K_INLINE kcham name##_Hash_Cb_Eq(name##Key* k1, name##Key* k2) { return func2(k1, k2); }
#define K_HASH_EQ_PURE(name)\
	K_INLINE kcham name##_Hash_Cb_Eq(name##Key* k1, name##Key* k2) { return *k1==*k2; }

#define K_HASH_KEY(name,func1)\
	K_INLINE void name##_Hash_Cb_Key(name##Key* key) { func1(key); }
#define K_HASH_KEY_DELETE(name)\
	K_INLINE void name##_Hash_Cb_Key(name##Key* key) { k_delete(*key); }
#define K_HASH_KEY_NONE(name)\
	K_INLINE void name##_Hash_Cb_Key(name##Key* key) { (void)key; }

#define K_HASH_VALUE(name,func1)\
	K_INLINE void name##_Hash_Cb_Value(name##Value* value) { func1(value); }
#define K_HASH_VALUE_DELETE(name)\
	K_INLINE void name##_Hash_Cb_Value(name##Value* value) { k_delete(*value); }
#define K_HASH_VALUE_NONE(name)\
	K_INLINE void name##_Hash_Cb_Value(name##Value* value) { (void)value; }

#define K_HASH_BOTH_NONE(name)\
	K_HASH_KEY_NONE(name);\
	K_HASH_VALUE_NONE(name)

#define K_HASH_HASHER_INT(name)\
	K_INLINE ksize_t name##_Hash_Cb_Hash(kint* key) { return K_CAST_INT_TO_UINT(*key); }\
	K_INLINE kcham name##_Hash_Cb_Eq(kint* k1, kint* k2) { return (*k1)==(*k2); }
#define K_HASH_HASHER_UINT(name)\
	K_INLINE ksize_t name##_Hash_Cb_Hash(kuint* key) { return *key; }\
	K_INLINE kcham name##_Hash_Cb_Eq(kuint* k1, kuint* k2) { return ((kint)*k1)==((kint)*k2); }
#define K_HASH_HASHER_SIZET(name)\
	K_INLINE ksize_t name##_Hash_Cb_Hash(ksize_t* key) { return (kuintptr)*key; }\
	K_INLINE kcham name##_Hash_Cb_Eq(ksize_t* k1, ksize_t* k2) { return (*k1)==(*k2); }
#define K_HASH_HASHER_CHAR_PTR(name)\
	K_INLINE ksize_t name##_Hash_Cb_Hash(kconstpointer key) { return k_strhash(*(const char**)key); }\
	K_INLINE kcham name##_Hash_Cb_Eq(kconstpointer k1, kconstpointer k2) { return k_strcmp(*(const char**)k1, *(const char**)k2)==0; }
#define K_HASH_HASHER_WCHAR_PTR(name)\
	K_INLINE ksize_t name##_Hash_Cb_Hash(kconstpointer key) { return k_wcshash(*(const kwchar**)key); }\
	K_INLINE kcham name##_Hash_Cb_Eq(kconstpointer k1, kconstpointer k2) { return k_wcscmp(*(const kwchar**)k1, *(const kwchar**)k2)==0; }
#define K_HASH_HASHER_CHAR_PTR_INCASE(name)\
	K_INLINE ksize_t name##_Hash_Cb_Hash(const char** key) { return k_strihash(*key); }\
	K_INLINE kcham name##_Hash_Cb_Eq(const char** k1, const char** k2) { return k_stricmp(*k1, *k2)==0; }
#define K_HASH_HASHER_WCHAR_PTR_INCASE(name)\
	K_INLINE ksize_t name##_Hash_Cb_Hash(const kwchar** key) { return k_wcsihash(*key); }\
	K_INLINE kcham name##_Hash_Cb_Eq(const kwchar** k1, const kwchar** k2) { return k_wcsicmp(*k1, *k2)==0; }

#define K_HASH_PTR_HASH(name,func1)\
	K_INLINE ksize_t name##_Hash_Cb_PtrHash(name##Key key) { return func1(key); }
#define K_HASH_PTR_HASH_PURE(name)\
	K_INLINE ksize_t name##_Hash_Cb_PtrHash(name##Key key) { return K_CAST_PTR_TO_SIZE(key); }

#define K_HASH_PTR_EQ(name,func2)\
	K_INLINE kcham name##_Hash_Cb_PtrEq(name##Key k1, name##Key k2) { return func2(k1, k2); }
#define K_HASH_PTR_EQ_PURE(name)\
	K_INLINE kcham name##_Hash_Cb_PtrEq(name##Key k1, name##Key k2) { return k1==k2; }

#define K_HASH_PTR_KEY(name,func1)\
	K_INLINE void name##_Hash_Cb_PtrKey(name##Key key) { func1(key); }
#define K_HASH_PTR_KEY_DELETE(name)\
	K_INLINE void name##_Hash_Cb_PtrKey(name##Key key) { k_delete(key); }
#define K_HASH_PTR_KEY_NONE(name)\
	K_INLINE void name##_Hash_Cb_PtrKey(name##Key key) { (void)key; }

#define K_HASH_PTR_VALUE(name,func1)\
	K_INLINE void name##_Hash_Cb_PtrValue(name##Value value) { func1(value); }
#define K_HASH_PTR_VALUE_DELETE(name)\
	K_INLINE void name##_Hash_Cb_PtrValue(name##Value value) { k_delete(value); }
#define K_HASH_PTR_VALUE_NONE(name)\
	K_INLINE void name##_Hash_Cb_PtrValue(name##Value value) { (void)value; }

#define K_HASH_PTR_BOTH_NONE(name)\
	K_HASH_PTR_KEY_NONE(name);\
	K_HASH_PTR_VALUE_NONE(name)

#define K_HASH_PTR_HASHER_CHAR_PTR(name)\
	K_INLINE ksize_t name##_Hash_Cb_PtrHash(const char* key) { return k_strhash(key); }\
	K_INLINE kcham name##_Hash_Cb_PtrEq(const char* k1, const char* k2) { return k_strcmp(k1, k2)==0; }
#define K_HASH_PTR_HASHER_WCHAR_PTR(name)\
	K_INLINE ksize_t name##_Hash_Cb_PtrHash(const kwchar* key) { return k_wcshash(key); }\
	K_INLINE kcham name##_Hash_Cb_PtrEq(const kwchar* k1, const kwchar* k2) { return k_wcscmp(k1, k2)==0; }

//
#define k_hash_count(p)					((p)->count)
#define k_hash_bucket(p)				((p)->bucket)
#define k_hash_revision(p)				((p)->revision)
#define k_hash_node_first(p)			((p)->last)
#define k_hash_node_last(p)				((p)->frst)

#define k_hash_init(name,p)\
	K_STMT_BEGIN{\
		(p)->revision=0;\
		(p)->count=0;\
		(p)->bucket=K_MIN_HASH;\
		(p)->nodes=k_new_zero(K_MIN_HASH, struct name##Node*);\
		(p)->frst=(p)->last=NULL;\
	}K_STMT_END

//
#define k_hash_disp(name,p)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		struct name##Node* __next;\
		for (__node=(p)->frst; __node; __node=__next)\
		{\
			__next=__node->next;\
			name##_Hash_Cb_Key(&__node->key);\
			name##_Hash_Cb_Value(&__node->value);\
			k_delete(__node);\
		}\
		k_delete((p)->nodes);\
	}K_STMT_END

#define k_hash_remove_node(name,p,node)\
	K_STMT_BEGIN{\
		struct name##Node** __en=&(node);\
		k_hash_inl_erase_node(name,p,&__en);\
		k_hash_inl_test_size(name,p);\
	}K_STMT_END

#define k_hash_clear(name,p)\
	K_STMT_BEGIN{\
		k_hash_inl_erase_all(name,p);\
		k_hash_inl_test_size(name,p);\
	}K_STMT_END

#define k_hash_foreach(name,p,func3,userdata)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		for (__node=(p)->last; __node; __node=__node->prev)\
			func3(userdata, &__node->key, &__node->value);\
	}K_STMT_END

#define k_hash_loopeach(name,p,func2)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		for (__node=(p)->last; __node; __node=__node->prev)\
			func2(&__node->key, &__node->value);\
	}K_STMT_END

#define k_hash_foreach_value(name,p,func2,userdata)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		for (__node=(p)->last; __node; __node=__node->prev)\
			func2(userdata, &__node->value);\
	}K_STMT_END

#define k_hash_loopeach_value(name,p,func1)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		for (__node=(p)->last; __node; __node=__node->prev)\
			func1(&__node->value);\
	}K_STMT_END

#define k_hash_node(name,p,keyptr,retnode)\
	K_STMT_BEGIN{\
		struct name##Node** __gn;\
		k_hash_inl_lookup(name,p,keyptr,__gn);\
		(retnode)=*__gn;\
	}K_STMT_END

#define k_hash_get(name,p,keyptr,retvalue)\
	K_STMT_BEGIN{\
		/* retvalue: pointer of 'value' */\
		struct name##Node** __gn;\
		struct name##Node* __node;\
		k_hash_inl_lookup(name,p,keyptr,__gn);\
		__node=*__gn;\
		*(retvalue)=(__node) ? &__node->value : NULL;\
	}K_STMT_END

#define k_hash_add(name,p,keyptr,valueptr)\
	k_hash_inl_set(name,p,keyptr,valueptr,FALSE)

#define k_hash_set(name,p,keyptr,valueptr)\
	k_hash_inl_set(name,p,keyptr,valueptr,TRUE);

#define k_hash_remove(name,p,keyptr,retcham_can_be_null)\
	K_STMT_BEGIN{\
		k_hash_inl_erase(name,p,keyptr,retcham_can_be_null);\
		k_hash_inl_test_size(name,p);\
	}K_STMT_END

#define k_hash_find(name,p,func,userdata,retkey,gotoname)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		for (__node=(p)->last; __node; __node=__node->prev)\
		{\
			if (func(userdata, &__node->key, &__node->value))\
			{\
				retkey=&__node->key;\
				goto K_CONCAT(pos_hash_find_exit,gotoname);\
			}\
		}\
		retkey=NULL;\
		K_CONCAT(pos_hash_find_exit,gotoname):;\
	}K_STMT_END

//
#define k_hash_inl_lookup(name,p,keyptr,retnode)\
	K_STMT_BEGIN{\
		/* keyptr: pointer of key */\
		/* retnode: pointer's pointer of Node */\
		ksize_t __lh=name##_Hash_Cb_Hash(keyptr);\
		struct name##Node** __ln=&(p)->nodes[__lh%(p)->bucket];\
		struct name##Node* __lnn;\
		while ((__lnn=*__ln)!=NULL)\
		{\
			if (__lnn->hash==__lh && name##_Hash_Cb_Eq(&__lnn->key, keyptr))\
				break;\
			__ln=&__lnn->sib;\
		}\
		(retnode)=__ln;\
	}K_STMT_END

#define k_hash_inl_lookup_hash(name,p,keyptr,retnode,rethash)\
	K_STMT_BEGIN{\
		/* keyptr: pointer of key */\
		/* retnode: pointer's pointer of Node */\
		/* rethash: pointer of kuint */\
		ksize_t __lh=name##_Hash_Cb_Hash(keyptr);\
		struct name##Node** __ln=&(p)->nodes[__lh%(p)->bucket];\
		struct name##Node* __lnn;\
		while ((__lnn=*__ln)!=NULL)\
		{\
			if (__lnn->hash==__lh && name##_Hash_Cb_Eq(&__lnn->key, keyptr))\
				break;\
			__ln=&__lnn->sib;\
		}\
		(retnode)=__ln;\
		*(rethash)=__lh;\
	}K_STMT_END

#define k_hash_inl_set(name,p,keyptr,valueptr,replace)\
	K_STMT_BEGIN{\
		/* keyptr: pointer of key */\
		/* valuedata : data of value */\
		/* replace: true=replace original key, false=discard given key */\
		ksize_t __ah;\
		struct name##Node** __an;\
		struct name##Node* __ann;\
		k_hash_inl_lookup_hash(name,p,keyptr,__an,&__ah);\
		__ann=*__an;\
		if (__ann)\
		{\
			if (replace)\
			{\
				name##_Hash_Cb_Key(&__ann->key);\
				__ann->key=*(keyptr);\
				name##_Hash_Cb_Value(&__ann->value);\
				__ann->value=*(valueptr);\
			}\
			else\
			{\
				name##_Hash_Cb_Key(keyptr);\
				name##_Hash_Cb_Value(valueptr);\
			}\
		}\
		else\
		{\
			/* step 1*/\
			__ann=k_new_1(struct name##Node);\
			__ann->sib=NULL;\
			__ann->hash=__ah;\
			__ann->key=*(keyptr);\
			__ann->value=*(valueptr);\
			/* step 2*/\
			if ((p)->frst)\
				(p)->frst->prev=__ann;\
			else\
				(p)->last=__ann;\
			__ann->next=(p)->frst;\
			__ann->prev=NULL;\
			(p)->frst=__ann;\
			/* step 3 */\
			*__an=__ann;\
			(p)->revision++;\
			(p)->count++;\
			/* step 4 */\
			k_hash_inl_test_size(name,p);\
		}\
	}K_STMT_END

#define k_hash_inl_erase(name,p,keyptr,retcham)\
	K_STMT_BEGIN{\
		struct name##Node** __rn;\
		k_hash_inl_lookup(name,p,keyptr,__rn);\
		if (*__rn==NULL)\
		{\
			if (retcham)\
			{\
				kcham* __c=retcham;\
				*__c=FALSE;\
			}\
		}\
		else\
		{\
			k_hash_inl_erase_node(name,p,&__rn);\
			if (retcham)\
			{\
				kcham* __c=retcham;\
				*__c=TRUE;\
			}\
		}\
	}K_STMT_END

#define k_hash_inl_erase_node(name,p,pppnode)\
	K_STMT_BEGIN{\
		struct name##Node** __en=*pppnode;\
		struct name##Node* __enn=*__en;\
		/* step 1 */\
		*__en=__enn->sib;\
		/* step 2 */\
		if (__enn->next)\
			__enn->next->prev=__enn->prev;\
		else\
		{\
			k_assert_eq((p)->last, __enn);\
			(p)->last=__enn->prev;\
		}\
		if (__enn->prev)\
			__enn->prev->next=__enn->next;\
		else\
		{\
			k_assert_eq((p)->frst, __enn);\
			(p)->frst=__enn->next;\
		}\
		/* step3 */\
		name##_Hash_Cb_Key(&__enn->key);\
		name##_Hash_Cb_Value(&__enn->value);\
		k_delete(__enn);\
		(p)->count--;\
		(p)->revision++;\
	}K_STMT_END

#define k_hash_inl_erase_all(name,p)\
	K_STMT_BEGIN{\
		struct name##Node* __enn;\
		struct name##Node* __enx;\
		for (__enn=(p)->frst; __enn; __enn=__enx)\
		{\
			__enx=__enn->next;\
			name##_Hash_Cb_Key(&__enn->key);\
			name##_Hash_Cb_Value(&__enn->value);\
			k_delete(__enn);\
		}\
		(p)->frst=(p)->last=NULL;\
		(p)->count=0;\
		memset((p)->nodes, 0, (p)->bucket*sizeof(struct name##Node*));\
	}K_STMT_END

//
#define k_hash_ptr_disp(name,p)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		struct name##Node* __next;\
		for (__node=(p)->frst; __node; __node=__next)\
		{\
			__next=__node->next;\
			name##_Hash_Cb_PtrKey(__node->key);\
			name##_Hash_Cb_PtrValue(__node->value);\
			k_delete(__node);\
		}\
		k_delete((p)->nodes);\
	}K_STMT_END

#define k_hash_ptr_remove_node(name,p,node)\
	K_STMT_BEGIN{\
		struct name##Node** __en=&(node);\
		k_hash_inl_ptr_erase_node(name,p,&__en);\
		k_hash_inl_test_size(name,p);\
	}K_STMT_END

#define k_hash_ptr_clear(name,p)\
	K_STMT_BEGIN{\
		k_hash_inl_ptr_erase_all(name,p);\
		k_hash_inl_test_size(name,p);\
	}K_STMT_END

#define k_hash_ptr_foreach(name,p,func3,userdata)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		for (__node=(p)->last; __node; __node=__node->prev)\
			func3(userdata, __node->key, __node->value);\
	}K_STMT_END

#define k_hash_ptr_loopeach(name,p,func2)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		for (__node=(p)->last; __node; __node=__node->prev)\
			func2(__node->key, __node->value);\
	}K_STMT_END

#define k_hash_ptr_foreach_value(name,p,func2,userdata)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		for (__node=(p)->last; __node; __node=__node->prev)\
			func2(userdata, __node->value);\
	}K_STMT_END

#define k_hash_ptr_loopeach_value(name,p,func1)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		for (__node=(p)->last; __node; __node=__node->prev)\
			func1(__node->value);\
	}K_STMT_END

#define k_hash_ptr_loopeach_inv_value(name,p,func1)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		for (__node=(p)->frst; __node; __node=__node->next)\
			func1(__node->value);\
	}K_STMT_END

#define k_hash_ptr_node(name,p,keyptr,retnode)\
	K_STMT_BEGIN{\
		struct name##Node** __gn;\
		k_hash_inl_ptr_lookup(name,p,keyptr,__gn);\
		(retnode)=*__gn;\
	}K_STMT_END

#define k_hash_ptr_get(name,p,keyptr,retvalue)\
	K_STMT_BEGIN{\
		/* retvalue: pointer of 'value' */\
		struct name##Node** __gn;\
		struct name##Node* __node;\
		k_hash_inl_ptr_lookup(name,p,keyptr,__gn);\
		__node=*__gn;\
		*(retvalue)=(__node) ? __node->value : NULL;\
	}K_STMT_END

#define k_hash_ptr_add(name,p,keyptr,valueptr)\
	k_hash_inl_ptr_set(name,p,keyptr,valueptr,FALSE)

#define k_hash_ptr_set(name,p,keyptr,valueptr)\
	k_hash_inl_ptr_set(name,p,keyptr,valueptr,TRUE);

#define k_hash_ptr_remove(name,p,keyptr,retcham_can_be_null)\
	K_STMT_BEGIN{\
		k_hash_inl_ptr_erase(name,p,keyptr,retcham_can_be_null);\
		k_hash_inl_test_size(name,p);\
	}K_STMT_END

//
#define k_hash_inl_ptr_lookup(name,p,keyptr,retnode)\
	K_STMT_BEGIN{\
		/* keyptr: pointer of key */\
		/* retnode: pointer's pointer of Node */\
		ksize_t __lh=name##_Hash_Cb_PtrHash(keyptr);\
		struct name##Node** __ln=&(p)->nodes[__lh%(p)->bucket];\
		struct name##Node* __lnn;\
		while ((__lnn=*__ln)!=NULL)\
		{\
			if (__lnn->hash==__lh && name##_Hash_Cb_PtrEq(__lnn->key, keyptr))\
				break;\
			__ln=&__lnn->sib;\
		}\
		(retnode)=__ln;\
	}K_STMT_END

#define k_hash_inl_ptr_lookup_hash(name,p,keyptr,retnode,rethash)\
	K_STMT_BEGIN{\
		/* keyptr: pointer of key */\
		/* retnode: pointer's pointer of Node */\
		/* rethash: pointer of kuint */\
		ksize_t __lh=name##_Hash_Cb_PtrHash(keyptr);\
		struct name##Node** __ln=&(p)->nodes[__lh%(p)->bucket];\
		struct name##Node* __lnn;\
		while ((__lnn=*__ln)!=NULL)\
		{\
			if (__lnn->hash==__lh && name##_Hash_Cb_PtrEq(__lnn->key, keyptr))\
				break;\
			__ln=&__lnn->sib;\
		}\
		(retnode)=__ln;\
		*(rethash)=__lh;\
	}K_STMT_END

#define k_hash_inl_ptr_set(name,p,keyptr,valueptr,replace)\
	K_STMT_BEGIN{\
		/* keyptr: pointer of key */\
		/* valuedata : data of value */\
		/* replace: true=replace original key, false=discard given key */\
		ksize_t __ah;\
		struct name##Node** __an;\
		struct name##Node* __ann;\
		k_hash_inl_ptr_lookup_hash(name,p,keyptr,__an,&__ah);\
		__ann=*__an;\
		if (__ann)\
		{\
			if (replace)\
			{\
				name##_Hash_Cb_PtrKey(__ann->key);\
				__ann->key=keyptr;\
				name##_Hash_Cb_PtrValue(__ann->value);\
				__ann->value=valueptr;\
			}\
			else\
			{\
				name##_Hash_Cb_PtrKey(keyptr);\
				name##_Hash_Cb_PtrValue(valueptr);\
			}\
		}\
		else\
		{\
			/* step 1*/\
			__ann=k_new_1(struct name##Node);\
			__ann->sib=NULL;\
			__ann->hash=__ah;\
			__ann->key=keyptr;\
			__ann->value=valueptr;\
			/* step 2*/\
			if ((p)->frst)\
				(p)->frst->prev=__ann;\
			else\
				(p)->last=__ann;\
			__ann->next=(p)->frst;\
			__ann->prev=NULL;\
			(p)->frst=__ann;\
			/* step 3 */\
			*__an=__ann;\
			(p)->revision++;\
			(p)->count++;\
			/* step 4 */\
			k_hash_inl_test_size(name,p);\
		}\
	}K_STMT_END

#define k_hash_inl_ptr_erase(name,p,keyptr,retcham)\
	K_STMT_BEGIN{\
		struct name##Node** __rn;\
		k_hash_inl_ptr_lookup(name,p,keyptr,__rn);\
		if (*__rn==NULL)\
		{\
			if (retcham)\
			{\
				kcham* __c=retcham;\
				*__c=FALSE;\
			}\
		}\
		else\
		{\
			k_hash_inl_ptr_erase_node(name,p,&__rn);\
			if (retcham)\
			{\
				kcham* __c=retcham;\
				*__c=TRUE;\
			}\
		}\
	}K_STMT_END

#define k_hash_inl_ptr_erase_node(name,p,pppnode)\
	K_STMT_BEGIN{\
		struct name##Node** __en=*pppnode;\
		struct name##Node* __enn=*__en;\
		/* step 1 */\
		*__en=__enn->sib;\
		/* step 2 */\
		if (__enn->next)\
			__enn->next->prev=__enn->prev;\
		else\
		{\
			k_assert_eq((p)->last, __enn);\
			(p)->last=__enn->prev;\
		}\
		if (__enn->prev)\
			__enn->prev->next=__enn->next;\
		else\
		{\
			k_assert_eq((p)->frst, __enn);\
			(p)->frst=__enn->next;\
		}\
		/* step3 */\
		name##_Hash_Cb_PtrKey(__enn->key);\
		name##_Hash_Cb_PtrValue(__enn->value);\
		k_delete(__enn);\
		(p)->count--;\
		(p)->revision++;\
	}K_STMT_END

#define k_hash_inl_ptr_erase_all(name,p)\
	K_STMT_BEGIN{\
		struct name##Node* __enn;\
		struct name##Node* __enx;\
		for (__enn=(p)->frst; __enn; __enn=__enx)\
		{\
			__enx=__enn->next;\
			name##_Hash_Cb_PtrKey(__enn->key);\
			name##_Hash_Cb_PtrValue(__enn->value);\
			k_delete(__enn);\
		}\
		(p)->frst=(p)->last=NULL;\
		(p)->count=0;\
		memset((p)->nodes, 0, (p)->bucket*sizeof(struct name##Node*));\
	}K_STMT_END

//
#define k_hash_inl_test_size(name,p)\
	K_STMT_BEGIN{\
		ksize_t __cnt=(p)->count;\
		ksize_t __bkt=(p)->bucket;\
		if ((__bkt>=3*__cnt && __bkt>K_MIN_HASH) ||\
			(3*__bkt<=__cnt && __bkt<K_MAX_HASH))\
			k_hash_inl_resize((kHash*)p);\
	}K_STMT_END

K_INLINE void k_hash_inl_resize(kHash* p)
{
	ksize_t i, newbucket;
	kHashNode** newnodes;

	newbucket=k_primeclose(p->count);
	newbucket=K_CLAMP(newbucket, K_MIN_HASH, K_MAX_HASH);
	newnodes=k_new_zero(newbucket, kHashNode*);

	for (i=0; i<p->bucket; i++)
	{
		kHashNode* node;
		kHashNode* next;
		ksize_t hashmask;
		for (node=p->nodes[i]; node; node=next)
		{
			next=node->sib;
			hashmask=node->hash%newbucket;
			node->sib=newnodes[hashmask];
			newnodes[hashmask]=node;
		}
	}

	k_delete(p->nodes);
	p->nodes=newnodes;
	p->bucket=newbucket;
}


//////////////////////////////////////////////////////////////////////////
// mukum
typedef struct kMukumNode
{
	struct kMukumNode*	sib;
	ksize_t				hash;
	kuintptr			key;
	kuintptr			value;
} kMukumNode;

typedef struct kMukum
{
	ksize_t				revision;
	ksize_t				bucket;
	ksize_t				count;
	kMukumNode**		nodes;
} kMukum;

#define K_MUKUM_DECL(name,keytype,valuetype)\
	typedef keytype name##Key;\
	typedef valuetype name##Value;\
	typedef struct name##Node { struct name##Node* sib; ksize_t hash; name##Key key; name##Value value; } name##Node;\
	typedef struct name { ksize_t revision; ksize_t bucket; ksize_t count; struct name##Node** nodes; } name

#define K_MUKUM_HASH(name,func1)				K_HASH_HASH(name,func1)
#define K_MUKUM_HASH_PURE(name)					K_HASH_HASH_PURE(name)

#define K_MUKUM_EQ(name,func2)					K_HASH_EQ(name,func2)
#define K_MUKUM_EQ_PURE(name)					K_HASH_EQ_PURE(name)

#define K_MUKUM_KEY(name,func1)					K_HASH_KEY(name,func1)
#define K_MUKUM_KEY_DELETE(name)				K_HASH_KEY_DELETE(name)
#define K_MUKUM_KEY_NONE(name)					K_HASH_KEY_NONE(name)

#define K_MUKUM_VALUE(name,func1)				K_HASH_VALUE(name,func1)
#define K_MUKUM_VALUE_DELETE(name)				K_HASH_VALUE_DELETE(name)
#define K_MUKUM_VALUE_NONE(name)				K_HASH_VALUE_NONE(name))

#define K_MUKUM_BOTH_NONE(name)					K_HASH_BOTH_NONE(name)

#define K_MUKUM_HASHER_INT(name)				K_HASH_HASHER_INT(name)
#define K_MUKUM_HASHER_UINT(name)				K_HASH_HASHER_UINT(name)
#define K_MUKUM_HASHER_CHAR_PTR(name)			K_HASH_HASHER_CHAR_PTR(name)
#define K_MUKUM_HASHER_WCHAR_PTR(name)			K_HASH_HASHER_WCHAR_PTR(name)
#define K_MUKUM_HASHER_CHAR_PTR_INCASE(name)	K_HASH_HASHER_CHAR_PTR_INCASE(name)
#define K_MUKUM_HASHER_WCHAR_PTR_INCASE(name)	K_HASH_HASHER_WCHAR_PTR_INCASE(name)

#define K_MUKUM_PTR_HASH(name,func1)			K_HASH_PTR_HASH(name,func1)
#define K_MUKUM_PTR_HASH_PURE(name)				K_HASH_PTR_HASH_PURE(name)

#define K_MUKUM_PTR_EQ(name,func2)				K_HASH_PTR_EQ(name,func2)
#define K_MUKUM_PTR_EQ_PURE(name)				K_HASH_PTR_EQ_PURE(name)

#define K_MUKUM_PTR_KEY(name,func1)				K_HASH_PTR_KEY(name,func1)
#define K_MUKUM_PTR_KEY_DELETE(name)			K_HASH_PTR_KEY_DELETE(name)
#define K_MUKUM_PTR_KEY_NONE(name)				K_HASH_PTR_KEY_NONE(name)

#define K_MUKUM_PTR_VALUE(name,func1)			K_HASH_PTR_VALUE(name,func1)
#define K_MUKUM_PTR_VALUE_DELETE(name)			K_HASH_PTR_VALUE_DELETE(name)
#define K_MUKUM_PTR_VALUE_NONE(name)			K_HASH_PTR_VALUE_NONE(name)

#define K_MUKUM_PTR_BOTH_NONE(name)				K_HASH_PTR_BOTH_NONE(name)

#define K_MUKUM_PTR_HASHER_CHAR_PTR(name)		K_HASH_PTR_HASHER_CHAR_PTR(name)
#define K_MUKUM_PTR_HASHER_WCHAR_PTR(name)		K_HASH_PTR_HASHER_WCHAR_PTR(name)

//
#define k_mukum_count(p)					((p)->count)
#define k_mukum_bucket(p)					((p)->bucket)
#define k_mukum_revision(p)					((p)->revision)

#define k_mukum_init(name,p)\
	K_STMT_BEGIN{\
		(p)->revision=0;\
		(p)->count=0;\
		(p)->bucket=K_MIN_HASH;\
		(p)->nodes=k_new_zero(K_MIN_HASH, struct name##Node*);\
	}K_STMT_END

//
#define k_mukum_disp(name,p)\
	K_STMT_BEGIN{\
		ksize_t __i;\
		struct name##Node* __node;\
		struct name##Node* __next;\
		for (__i=0; __i<(p)->bucket; __i++)\
			for (__node=(p)->nodes[__i]; __node; __node=__next)\
			{\
				__next=__node->sib;\
				name##_Hash_Cb_Key(&__node->key);\
				name##_Hash_Cb_Value(&__node->value);\
				k_delete(__node);\
			}\
		k_delete((p)->nodes);\
	}K_STMT_END

#define k_mukum_remove_node(name,p,node)\
	K_STMT_BEGIN{\
		struct name##Node** __en=&(node);\
		k_mukum_inl_erase_node(name,p,&__en);\
		k_mukum_inl_test_size(name,p);\
	}K_STMT_END

#define k_mukum_clear(name,p)\
	K_STMT_BEGIN{\
		k_mukum_inl_erase_all(name,p);\
		k_mukum_inl_test_size(name,p);\
	}K_STMT_END

#define k_mukum_foreach(name,p,func3,userdata)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		ksize_t __i;\
		for (__i=0; __i<(p)->bucket; __i++)\
			for (__node=(p)->nodes[__i]; __node; __node=__node->sib)\
				func3(userdata, &__node->key, &__node->value);\
	}K_STMT_END

#define k_mukum_loopeach(name,p,func2)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		ksize_t __i;\
		for (__i=0; __i<(p)->bucket; __i++)\
			for (__node=(p)->nodes[__i]; __node; __node=__node->sib)\
				func2(&__node->key, &__node->value);\
	}K_STMT_END

#define k_mukum_foreach_value(name,p,func2,userdata)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		ksize_t __i;\
		for (__i=0; __i<(p)->bucket; __i++)\
			for (__node=(p)->nodes[__i]; __node; __node=__node->sib)\
				func2(userdata, &__node->value);\
	}K_STMT_END

#define k_mukum_loopeach_value(name,p,func1)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		ksize_t __i;\
		for (__i=0; __i<(p)->bucket; __i++)\
			for (__node=(p)->nodes[__i]; __node; __node=__node->sib)\
				func1(&__node->value);\
	}K_STMT_END

// value type
#define k_mukum_node(name,p,keyptr,retnode)\
	K_STMT_BEGIN{\
		struct name##Node** __gn;\
		k_mukum_inl_lookup(name,p,keyptr,__gn);\
		(retnode)=*__gn;\
	}K_STMT_END

#define k_mukum_get(name,p,keyptr,retvalue)\
	K_STMT_BEGIN{\
		/* retvalue: pointer of 'value' */\
		struct name##Node** __gn;\
		struct name##Node* __node;\
		k_mukum_inl_lookup(name,p,keyptr,__gn);\
		__node=*__gn;\
		*(retvalue)=(__node) ? &__node->value : NULL;\
	}K_STMT_END

#define k_mukum_add(name,p,keyptr,valueptr)\
	k_mukum_inl_set(name,p,keyptr,valueptr,FALSE);

#define k_mukum_set(name,p,keyptr,valueptr)\
	k_mukum_inl_set(name,p,keyptr,valueptr,TRUE);\

#define k_mukum_remove(name,p,keyptr,retcham_can_be_null)\
	K_STMT_BEGIN{\
		k_mukum_inl_erase(name,p,keyptr,retcham_can_be_null);\
		k_mukum_inl_test_size(name,p);\
	}K_STMT_END

#define k_mukum_find(name,p,func,userdata,retkey,gotoname)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		ksize_t __i;\
		for (__i=0; __i<(p)->bucket; __i++)\
		{\
			for (__node=(p)->nodes[__i]; __node; __node=__node->sib)\
			{\
				if (func(userdata, &__node->key, &__node->value))\
				{\
					retkey=&__node->key;\
					goto K_CONCAT(pos_mukum_find_exit,gotoname);\
				}\
			}\
		}\
		retkey=NULL;\
	K_CONCAT(pos_mukum_find_exit,gotoname):;\
	}K_STMT_END

//
#define k_mukum_inl_lookup(name,p,keyptr,retnode)\
	K_STMT_BEGIN{\
		/* keyptr: pointer of key */\
		/* retnode: pointer's pointer of Node */\
		ksize_t __lh=name##_Hash_Cb_Hash(keyptr);\
		struct name##Node** __ln=&(p)->nodes[__lh%(p)->bucket];\
		struct name##Node* __lnn;\
		while ((__lnn=*__ln)!=NULL)\
		{\
			if (__lnn->hash==__lh && name##_Hash_Cb_Eq(&__lnn->key, keyptr))\
				break;\
			__ln=&__lnn->sib;\
		}\
		(retnode)=__ln;\
	}K_STMT_END

#define k_mukum_inl_lookup_hash(name,p,keyptr,retnode,rethash)\
	K_STMT_BEGIN{\
		/* keyptr: pointer of key */\
		/* retnode: pointer's pointer of Node */\
		/* rethash: pointer of kuint */\
		ksize_t __lh=name##_Hash_Cb_Hash(keyptr);\
		struct name##Node** __ln=&(p)->nodes[__lh%(p)->bucket];\
		struct name##Node* __lnn;\
		while ((__lnn=*__ln)!=NULL)\
		{\
			if (__lnn->hash==__lh && name##_Hash_Cb_Eq(&__lnn->key, keyptr))\
				break;\
			__ln=&__lnn->sib;\
		}\
		(retnode)=__ln;\
		*(rethash)=__lh;\
	}K_STMT_END

#define k_mukum_inl_set(name,p,keyptr,valueptr,replace)\
	K_STMT_BEGIN{\
		/* keyptr: pointer of key */\
		/* valuedata : data of value */\
		/* replace: true=replace original key, false=discard given key */\
		ksize_t __ah;\
		struct name##Node** __an;\
		struct name##Node* __ann;\
		k_mukum_inl_lookup_hash(name,p,keyptr,__an,&__ah);\
		__ann=*__an;\
		if (__ann)\
		{\
			if (replace)\
			{\
				name##_Hash_Cb_Key(&__ann->key);\
				__ann->key=*(keyptr);\
				name##_Hash_Cb_Value(&__ann->value);\
				__ann->value=*(valueptr);\
			}\
			else\
			{\
				name##_Hash_Cb_Key(keyptr);\
				name##_Hash_Cb_Value(valueptr);\
			}\
		}\
		else\
		{\
			/* step 1*/\
			__ann=k_new_1(struct name##Node);\
			__ann->sib=NULL;\
			__ann->hash=__ah;\
			__ann->key=*(keyptr);\
			__ann->value=*(valueptr);\
			/* step 2 */\
			*__an=__ann;\
			(p)->revision++;\
			(p)->count++;\
			/* step 3 */\
			k_mukum_inl_test_size(name,p);\
		}\
	}K_STMT_END

#define k_mukum_inl_erase(name,p,keyptr,retcham)\
	K_STMT_BEGIN{\
		struct name##Node** __rn;\
		k_mukum_inl_lookup(name,p,keyptr,__rn);\
		if (*__rn==NULL)\
		{\
			if (retcham)\
			{\
				kcham* __c=retcham;\
				*__c=FALSE;\
			}\
		}\
		else\
		{\
			k_mukum_inl_erase_node(name,p,&__rn);\
			if (retcham)\
			{\
				kcham* __c=retcham;\
				*__c=TRUE;\
			}\
		}\
	}K_STMT_END

#define k_mukum_inl_erase_node(name,p,pppnode)\
	K_STMT_BEGIN{\
		struct name##Node** __en=*pppnode;\
		struct name##Node* __enn=*__en;\
		/* step 1 */\
		*__en=__enn->sib;\
		/* step 2 */\
		name##_Hash_Cb_Key(&__enn->key);\
		name##_Hash_Cb_Value(&__enn->value);\
		k_delete(__enn);\
		(p)->count--;\
		(p)->revision++;\
	}K_STMT_END

#define k_mukum_inl_erase_all(name,p)\
	K_STMT_BEGIN{\
		ksize_t __i;\
		struct name##Node* __node;\
		struct name##Node* __next;\
		for (__i=0; __i<(p)->bucket; __i++)\
			for (__node=(p)->nodes[__i]; __node; __node=__next)\
			{\
				__next=__node->sib;\
				name##_Hash_Cb_Key(&__node->key);\
				name##_Hash_Cb_Value(&__node->value);\
				k_delete(__node);\
			}\
		(p)->count=0;\
		(p)->revision++;\
		memset((p)->nodes, 0, (p)->bucket*sizeof(struct name##Node*));\
	}K_STMT_END

// 
#define k_mukum_ptr_disp(name,p)\
	K_STMT_BEGIN{\
		ksize_t __i;\
		struct name##Node* __node;\
		struct name##Node* __next;\
		for (__i=0; __i<(p)->bucket; __i++)\
			for (__node=(p)->nodes[__i]; __node; __node=__next)\
			{\
				__next=__node->sib;\
				name##_Hash_Cb_PtrKey(__node->key);\
				name##_Hash_Cb_PtrValue(__node->value);\
				k_delete(__node);\
			}\
		k_delete((p)->nodes);\
	}K_STMT_END

#define k_mukum_ptr_remove_node(name,p,node)\
	K_STMT_BEGIN{\
		struct name##Node** __en=&(node);\
		k_mukum_inl_ptr_erase_node(name,p,&__en);\
		k_mukum_inl_test_size(name,p);\
	}K_STMT_END

#define k_mukum_ptr_clear(name,p)\
	K_STMT_BEGIN{\
		k_mukum_inl_ptr_erase_all(name,p);\
		k_mukum_inl_test_size(name,p);\
	}K_STMT_END

#define k_mukum_ptr_foreach(name,p,func3,userdata)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		ksize_t __i;\
		for (__i=0; __i<(p)->bucket; __i++)\
			for (__node=(p)->nodes[__i]; __node; __node=__node->sib)\
				func3(userdata, __node->key, __node->value);\
	}K_STMT_END

#define k_mukum_ptr_loopeach(name,p,func2)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		ksize_t __i;\
		for (__i=0; __i<(p)->bucket; __i++)\
			for (__node=(p)->nodes[__i]; __node; __node=__node->sib)\
				func2(__node->key, __node->value);\
	}K_STMT_END

#define k_mukum_ptr_foreach_value(name,p,func2,userdata)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		ksize_t __i;\
		for (__i=0; __i<(p)->bucket; __i++)\
			for (__node=(p)->nodes[__i]; __node; __node=__node->sib)\
				func2(userdata, __node->value);\
	}K_STMT_END

#define k_mukum_ptr_loopeach_value(name,p,func1)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		ksize_t __i;\
		for (__i=0; __i<(p)->bucket; __i++)\
			for (__node=(p)->nodes[__i]; __node; __node=__node->sib)\
				func1(__node->value);\
	}K_STMT_END

// value type
#define k_mukum_ptr_node(name,p,keyptr,retnode)\
	K_STMT_BEGIN{\
		struct name##Node** __gn;\
		k_mukum_inl_ptr_lookup(name,p,keyptr,__gn);\
		(retnode)=*__gn;\
	}K_STMT_END

#define k_mukum_ptr_get(name,p,keyptr,retvalue)\
	K_STMT_BEGIN{\
		/* retvalue: pointer of 'value' */\
		struct name##Node** __gn;\
		struct name##Node* __node;\
		k_mukum_inl_ptr_lookup(name,p,keyptr,__gn);\
		__node=*__gn;\
		*(retvalue)=(__node) ? __node->value : NULL;\
	}K_STMT_END

#define k_mukum_ptr_add(name,p,keyptr,valueptr)\
	k_mukum_inl_ptr_set(name,p,keyptr,valueptr,FALSE)

#define k_mukum_ptr_set(name,p,keyptr,valueptr)\
	k_mukum_inl_ptr_set(name,p,keyptr,valueptr,TRUE)

#define k_mukum_ptr_remove(name,p,keyptr,retcham_can_be_null)\
	K_STMT_BEGIN{\
		k_mukum_inl_ptr_erase(name,p,keyptr,retcham_can_be_null);\
		k_mukum_inl_test_size(name,p);\
	}K_STMT_END

#define k_mukum_ptr_find(name,p,func,userdata,retkey,gotoname)\
	K_STMT_BEGIN{\
		struct name##Node* __node;\
		ksize_t __i;\
		for (__i=0; __i<(p)->bucket; __i++)\
		{\
			for (__node=(p)->nodes[__i]; __node; __node=__node->sib)\
			{\
				if (func(userdata, __node->key, __node->value))\
				{\
					*(retkey)=__node->key;\
					goto K_CONCAT(pos_mukum_find_exit,gotoname);\
				}\
			}\
		}\
		retkey=NULL;\
		K_CONCAT(pos_mukum_find_exit,gotoname):;\
	}K_STMT_END

//
#define k_mukum_inl_ptr_lookup(name,p,keyptr,retnode)\
	K_STMT_BEGIN{\
		/* keyptr: pointer of key */\
		/* retnode: pointer's pointer of Node */\
		ksize_t __lh=name##_Hash_Cb_PtrHash(keyptr);\
		struct name##Node** __ln=&(p)->nodes[__lh%(p)->bucket];\
		struct name##Node* __lnn;\
		while ((__lnn=*__ln)!=NULL)\
		{\
			if (__lnn->hash==__lh && name##_Hash_Cb_PtrEq(__lnn->key, keyptr))\
				break;\
			__ln=&__lnn->sib;\
		}\
		(retnode)=__ln;\
	}K_STMT_END

#define k_mukum_inl_ptr_lookup_hash(name,p,keyptr,retnode,rethash)\
	K_STMT_BEGIN{\
		/* keyptr: pointer of key */\
		/* retnode: pointer's pointer of Node */\
		/* rethash: pointer of kuint */\
		ksize_t __lh=name##_Hash_Cb_PtrHash(keyptr);\
		struct name##Node** __ln=&(p)->nodes[__lh%(p)->bucket];\
		struct name##Node* __lnn;\
		while ((__lnn=*__ln)!=NULL)\
		{\
			if (__lnn->hash==__lh && name##_Hash_Cb_PtrEq(__lnn->key, keyptr))\
				break;\
			__ln=&__lnn->sib;\
		}\
		(retnode)=__ln;\
		*(rethash)=__lh;\
	}K_STMT_END

#define k_mukum_inl_ptr_set(name,p,keyptr,valueptr,replace)\
	K_STMT_BEGIN{\
		/* keyptr: pointer of key */\
		/* valuedata : data of value */\
		/* replace: true=replace original key, false=discard given key */\
		ksize_t __ah;\
		struct name##Node** __an;\
		struct name##Node* __ann;\
		k_mukum_inl_ptr_lookup_hash(name,p,keyptr,__an,&__ah);\
		__ann=*__an;\
		if (__ann)\
		{\
			if (replace)\
			{\
				name##_Hash_Cb_PtrKey(__ann->key);\
				__ann->key=keyptr;\
				name##_Hash_Cb_PtrValue(__ann->value);\
				__ann->value=valueptr;\
			}\
			else\
			{\
				name##_Hash_Cb_PtrKey(keyptr);\
				name##_Hash_Cb_PtrValue(valueptr);\
			}\
		}\
		else\
		{\
			/* step 1*/\
			__ann=k_new_1(struct name##Node);\
			__ann->sib=NULL;\
			__ann->hash=__ah;\
			__ann->key=keyptr;\
			__ann->value=valueptr;\
			/* step 2 */\
			*__an=__ann;\
			(p)->revision++;\
			(p)->count++;\
			/* step 3 */\
			k_mukum_inl_test_size(name,p);\
		}\
	}K_STMT_END

#define k_mukum_inl_ptr_erase(name,p,keyptr,retcham)\
	K_STMT_BEGIN{\
		struct name##Node** __rn;\
		k_mukum_inl_ptr_lookup(name,p,keyptr,__rn);\
		if (*__rn==NULL)\
		{\
			if (retcham)\
			{\
				kcham* __c=retcham;\
				*__c=FALSE;\
			}\
		}\
		else\
		{\
			k_mukum_inl_ptr_erase_node(name,p,&__rn);\
			if (retcham)\
			{\
				kcham* __c=retcham;\
				*__c=TRUE;\
			}\
		}\
	}K_STMT_END

#define k_mukum_inl_ptr_erase_node(name,p,pppnode)\
	K_STMT_BEGIN{\
		struct name##Node** __en=*pppnode;\
		struct name##Node* __enn=*__en;\
		/* step 1 */\
		*__en=__enn->sib;\
		/* step 2 */\
		name##_Hash_Cb_PtrKey(__enn->key);\
		name##_Hash_Cb_PtrValue(__enn->value);\
		k_delete(__enn);\
		(p)->count--;\
		(p)->revision++;\
	}K_STMT_END

#define k_mukum_inl_ptr_erase_all(name,p)\
	K_STMT_BEGIN{\
		ksize_t __i;\
		struct name##Node* __node;\
		struct name##Node* __next;\
		for (__i=0; __i<(p)->bucket; __i++)\
			for (__node=(p)->nodes[__i]; __node; __node=__next)\
			{\
				__next=__node->sib;\
				name##_Hash_Cb_PtrKey(__node->key);\
				name##_Hash_Cb_PtrValue(__node->value);\
				k_delete(__node);\
			}\
		(p)->count=0;\
		(p)->revision++;\
		memset((p)->nodes, 0, (p)->bucket*sizeof(struct name##Node*));\
	}K_STMT_END

//
#define k_mukum_inl_test_size(name,p)\
	K_STMT_BEGIN{\
		ksize_t __cnt=(p)->count;\
		ksize_t __bkt=(p)->bucket;\
		if ((__bkt>=3*__cnt && __bkt>K_MIN_HASH) ||\
			(3*__bkt<=__cnt && __bkt<K_MAX_HASH))\
			k_mukum_inl_resize((kMukum*)p);\
	}K_STMT_END

K_INLINE void k_mukum_inl_resize(kMukum* p)
{
	ksize_t i, newbucket;
	kMukumNode** newnodes;

	newbucket=k_primeclose(p->count);
	newbucket=K_CLAMP(newbucket, K_MIN_HASH, K_MAX_HASH);
	newnodes=k_new_zero(newbucket, kMukumNode*);

	for (i=0; i<p->bucket; i++)
	{
		kMukumNode* node;
		kMukumNode* next;
		ksize_t hashmask;
		for (node=p->nodes[i]; node; node=next)
		{
			next=node->sib;
			hashmask=node->hash%newbucket;
			node->sib=newnodes[hashmask];
			newnodes[hashmask]=node;
		}
	}

	k_delete(p->nodes);
	p->nodes=newnodes;
	p->bucket=newbucket;
}


//////////////////////////////////////////////////////////////////////////
// blue string
typedef struct kBstr
{
	kint				len;
	char				data[];
} kBstr;

typedef struct kBstr64
{
	kint				len;
	char				data[64];
} kBstr64;

typedef struct kBstr260
{
	kint				len;
	char				data[260];
} kBstr260;

typedef struct kBstr1k
{
	kint				len;
	char				data[1024];
} kBstr1k;

typedef struct kBstr2k
{
	kint				len;
	char				data[2048];
} kBstr2k;

typedef struct kBstr4k
{
	kint				len;
	char				data[4096];
} kBstr4k;

typedef struct kBstr8k
{
	kint				len;
	char				data[8192];
} kBstr8k;

#define k_bstr_length(p)				(((kBstr*)(p))->len)
#define k_bstr_data(p)					(((kBstr*)(p))->data)
#define k_bstr_nth(p,n)					(((kBstr*)(p))->data[(n)])
#define k_bstr_inv(p,n)					(((kBstr*)(p))->data[(((kBstr*)(p))->len)-(n)-1])

K_INLINE void k_bstr_test_init(kpointer p)
{
	k_assert_0(((kBstr*)p)->len==0 && *((kBstr*)p)->data=='\0');
	(void)p;
}

K_INLINE void k_bstr_init(kpointer p, const char* str)
{
	if (str)
	{
		((kBstr*)p)->len=(kint)k_strlen(str);
		k_strcpy(((kBstr*)p)->data, str);
	}
	else
	{
		((kBstr*)p)->len=0;
		*((kBstr*)p)->data='\0';
	}
}

K_INLINE void k_bstr_zero(kpointer p)
{
	((kBstr*)p)->len=0;
	*((kBstr*)p)->data='\0';
}

K_INLINE kcham k_bstr_eq(kpointer p1, kpointer p2)
{
	return k_strcmp(((kBstr*)p1)->data, ((kBstr*)p2)->data)==0;
}

K_INLINE kpointer k_bstr_test_len(kpointer p)
{
	((kBstr*)p)->len=(kint)k_strlen(((kBstr*)p)->data);
	return p;
}

K_INLINE kpointer k_bstr_clear(kpointer p)
{
	((kBstr*)p)->len=0;
	*((kBstr*)p)->data='\0';
	return p;
}

K_INLINE kpointer k_bstr_set(kpointer p, const char* str)
{
	((kBstr*)p)->len=(kint)k_strlen(str);
	k_strcpy(((kBstr*)p)->data, str);
	return p;
}

K_INLINE kpointer k_bstr_set_safe(kpointer p, const char* str, kint max)
{
	((kBstr*)p)->len=(kint)k_strlen(str);
	if (((kBstr*)p)->len<(max-1))
		k_strcpy(((kBstr*)p)->data, str);
	else
	{
		((kBstr*)p)->len=max-1;
		k_strncpy(((kBstr*)p)->data, str, max-1);
	}
	return p;
}

K_INLINE kpointer k_bstr_set_bls(kpointer p, kconstpointer right)
{
	((kBstr*)p)->len=((const kBstr*)right)->len;
	k_strcpy(((kBstr*)p)->data, ((const kBstr*)right)->data);
	return p;
}

K_INLINE kpointer k_bstr_set_len(kpointer p, const char* str, kint len)
{
	if (len<0)
		return k_bstr_set(p, str);
	else
	{
		((kBstr*)p)->len=len;
		k_strncpy(((kBstr*)p)->data, str, len);
		return p;
	}
}

K_INLINE kpointer k_bstr_set_char(kpointer p, char ch)
{
	((kBstr*)p)->len=1;
	((kBstr*)p)->data[0]=ch;
	((kBstr*)p)->data[1]='\0';
	return p;
}

K_INLINE kpointer k_bstr_set_rep(kpointer p, kint ch, kint cnt)
{
	((kBstr*)p)->len=(kint)k_strfll(((kBstr*)p)->data, 0, cnt, ch);
	((kBstr*)p)->data[cnt]='\0';
	return p;
}

K_INLINE kpointer k_bstr_append(kpointer p, const char* str)
{
	k_strcpy(&((kBstr*)p)->data[((kBstr*)p)->len], str);
	((kBstr*)p)->len+=(kint)k_strlen(str);
	return p;
}

K_INLINE kpointer k_bstr_append_bls(kpointer p, kconstpointer right)
{
	k_strcpy(&((kBstr*)p)->data[((kBstr*)p)->len], ((const kBstr*)right)->data);
	((kBstr*)p)->len+=((const kBstr*)right)->len;
	return p;
}

K_INLINE kpointer k_bstr_append_char(kpointer p, kint ch)
{
	((kBstr*)p)->data[((kBstr*)p)->len++]=(char)ch;
	((kBstr*)p)->data[((kBstr*)p)->len]='\0';
	return p;
}

K_INLINE kpointer k_bstr_append_rep(kpointer p, kint ch, kint cnt)
{
	((kBstr*)p)->len=(kint)k_strfll(((kBstr*)p)->data, ((kBstr*)p)->len, ((kBstr*)p)->len+cnt, ch);
	((kBstr*)p)->data[((kBstr*)p)->len]='\0';
	return p;
}

K_INLINE kcham k_bstr_is_empty(kconstpointer p)
{
	return ((const kBstr*)p)->len==0;
}

K_INLINE kcham k_bstr_is_have(kconstpointer p)
{
	return ((const kBstr*)p)->len!=0;
}

K_INLINE size_t k_bstr_hash(kconstpointer p)
{
	return k_strhash(((const kBstr*)p)->data);
}

K_INLINE kint k_bstr_compare(kconstpointer p, const char* s, kcham igcase)
{
	if (igcase)
		return k_stricmp(((const kBstr*)p)->data, s);
	else
		return k_strcmp(((const kBstr*)p)->data, s);
}

K_INLINE kint k_bstr_compare_bls(kconstpointer p1, kconstpointer p2, kcham igcase)
{
	if (igcase)
		return k_stricmp(((const kBstr*)p1)->data, ((const kBstr*)p2)->data);
	else
		return k_strcmp(((const kBstr*)p1)->data, ((const kBstr*)p2)->data);
}

K_INLINE kint k_bstr_compare_bls_length(kconstpointer p1, kconstpointer p2, kint len, kcham igcase)
{
	if (igcase)
		return k_strnicmp(((const kBstr*)p1)->data, ((const kBstr*)p2)->data, len);
	else
		return k_strncmp(((const kBstr*)p1)->data, ((const kBstr*)p2)->data, len);
}

K_INLINE void k_bstr_format(kpointer p, kint size, const char* fmt, ...)
{
	va_list va;
	va_start(va, fmt);
	((kBstr*)p)->len=k_vsnprintf(((kBstr*)p)->data, size-1, fmt, va);
	va_end(va);
}

K_INLINE void k_bstr_format_va(kpointer p, kint size, const char* fmt, va_list va)
{
	((kBstr*)p)->len=k_vsnprintf(((kBstr*)p)->data, size-1, fmt, va);
}

K_INLINE void k_bstr_append_format(kpointer p, kint size, const char* fmt, ...)
{
	va_list va;
	va_start(va, fmt);
	((kBstr*)p)->len+=k_vsnprintf(((kBstr*)p)->data+((kBstr*)p)->len, size-1-((kBstr*)p)->len, fmt, va);
	va_end(va);
}

K_INLINE void k_bstr_append_format_va(kpointer p, kint size, const char* fmt, va_list va)
{
	((kBstr*)p)->len+=k_vsnprintf(((kBstr*)p)->data+((kBstr*)p)->len, size-1-((kBstr*)p)->len, fmt, va);
}

K_INLINE kint k_bstr_has_char(kconstpointer p, const char* chars)
{
	char* s=k_strbrk(((kBstr*)p)->data, chars);
	return (s) ? (kint)(s-((kBstr*)p)->data) : -1;
}

K_INLINE kint k_bstr_find_char(kconstpointer p, int at, char ch)
{
	char* s=k_strchr(((kBstr*)p)->data+at, ch);
	return (s) ? (kint)(s-((kBstr*)p)->data) : -1;
}

K_INLINE kcham k_bstr_sub_bls(kpointer p, kconstpointer s, kint pos, kint len)
{
	k_return_value_if_fail(pos>=0, FALSE);
	k_return_value_if_fail(((const kBstr*)s)->len>=pos, FALSE);

	if (len>0)
	{
		k_return_value_if_fail(((const kBstr*)s)->len>=(pos+len), FALSE);
	}
	else
	{
		len=((const kBstr*)s)->len-pos;
	}

	k_strmid(((kBstr*)p)->data, ((const kBstr*)s)->data, pos, len);
	((kBstr*)p)->len=len;
	return TRUE;
}

K_INLINE void k_bstr_upper(kpointer p)
{
	k_strupr(((kBstr*)p)->data);
}

K_INLINE void k_bstr_lower(kpointer p)
{
	k_strlwr(((kBstr*)p)->data);
}

K_INLINE void k_bstr_trim(kpointer p)
{
	k_strtrim(((kBstr*)p)->data);
	((kBstr*)p)->len=(kint)k_strlen(((kBstr*)p)->data);
}

K_INLINE void k_bstr_trim_left(kpointer p)
{
	k_strltrim(((kBstr*)p)->data);
	((kBstr*)p)->len=(kint)k_strlen(((kBstr*)p)->data);
}

K_INLINE void k_bstr_trim_right(kpointer p)
{
	k_strrtrim(((kBstr*)p)->data);
	((kBstr*)p)->len=(kint)k_strlen(((kBstr*)p)->data);
}

K_INLINE void k_bstr_rem_chars(kpointer p, const char* rmlist)
{
	((kBstr*)p)->len=(kint)k_strlen(k_strrem(((kBstr*)p)->data, rmlist));
}


//////////////////////////////////////////////////////////////////////////
// blue wcs
typedef struct kBwcs
{
	kint				len;
	kwchar				data[];
} kBwcs;

typedef struct kBwcs64
{
	kint				len;
	kwchar				data[64];
} kBwcs64;

typedef struct kBwcs260
{
	kint				len;
	kwchar				data[260];
} kBwcs260;

typedef struct kBwcs1k
{
	kint				len;
	kwchar				data[1024];
} kBwcs1k;

typedef struct kBwcs2k
{
	kint				len;
	kwchar				data[2048];
} kBwcs2k;

typedef struct kBwcs4k
{
	kint				len;
	kwchar				data[4096];
} kBwcs4k;

typedef struct kBwcs8k
{
	kint				len;
	kwchar				data[8192];
} kBwcs8k;

#define k_bwcs_length(p)				(((kBwcs*)(p))->len)
#define k_bwcs_data(p)					(((kBwcs*)(p))->data)
#define k_bwcs_nth(p,n)					(((kBwcs*)(p))->data[(n)])

K_INLINE void k_bwcs_test_init(kpointer p)
{
	k_assert_0(((kBwcs*)p)->len==0 && *((kBwcs*)p)->data==L'\0');
	(void)p;
}

K_INLINE void k_bwcs_init(kpointer p, const kwchar* str)
{
	if (str)
	{
		((kBwcs*)p)->len=(kint)k_wcslen(str);
		k_wcscpy(((kBwcs*)p)->data, str);
	}
	else
	{
		((kBwcs*)p)->len=0;
		*((kBwcs*)p)->data=L'\0';
	}
}

K_INLINE void k_bwcs_zero(kpointer p)
{
	((kBwcs*)p)->len=0;
	*((kBwcs*)p)->data=L'\0';
}

K_INLINE kcham k_bwcs_eq(kpointer p1, kpointer p2)
{
	return k_wcscmp(((kBwcs*)p1)->data, ((kBwcs*)p2)->data)==0;
}

K_INLINE kpointer k_bwcs_test_len(kpointer p)
{
	((kBwcs*)p)->len=(kint)k_wcslen(((kBwcs*)p)->data);
	return p;
}

K_INLINE kpointer k_bwcs_clear(kpointer p)
{
	((kBwcs*)p)->len=0;
	*((kBwcs*)p)->data=L'\0';
	return p;
}

K_INLINE kpointer k_bwcs_set(kpointer p, const kwchar* str)
{
	((kBwcs*)p)->len=(kint)k_wcslen(str);
	k_wcscpy(((kBwcs*)p)->data, str);
	return p;
}

K_INLINE kpointer k_bwcs_set_bls(kpointer p, kconstpointer right)
{
	((kBwcs*)p)->len=((const kBwcs*)right)->len;
	k_wcscpy(((kBwcs*)p)->data, ((const kBwcs*)right)->data);
	return p;
}

K_INLINE kpointer k_bwcs_set_len(kpointer p, const kwchar* str, kint len)
{
	if (len<0)
		return k_bwcs_set(p, str);
	else
	{
		((kBwcs*)p)->len=len;
		k_wcsncpy(((kBwcs*)p)->data, str, len);
		return p;
	}
}

K_INLINE kpointer k_bwcs_set_char(kpointer p, kwchar ch)
{
	((kBwcs*)p)->len=1;
	((kBwcs*)p)->data[0]=ch;
	((kBwcs*)p)->data[1]=L'\0';
	return p;
}

K_INLINE kpointer k_bwcs_set_rep(kpointer p, kint ch, kint cnt)
{
	((kBwcs*)p)->len=(kint)k_wcsfll(((kBwcs*)p)->data, 0, cnt, ch);
	((kBwcs*)p)->data[cnt]=L'\0';
	return p;
}

K_INLINE kpointer k_bwcs_append(kpointer p, const kwchar* str)
{
	k_wcscpy(&((kBwcs*)p)->data[((kBwcs*)p)->len], str);
	((kBwcs*)p)->len+=(kint)k_wcslen(str);
	return p;
}

K_INLINE kpointer k_bwcs_append_bls(kpointer p, kconstpointer right)
{
	k_wcscpy(&((kBwcs*)p)->data[((kBwcs*)p)->len], ((const kBwcs*)right)->data);
	((kBwcs*)p)->len+=((const kBwcs*)right)->len;
	return p;
}

K_INLINE kpointer k_bwcs_append_char(kpointer p, kwchar ch)
{
	((kBwcs*)p)->data[((kBwcs*)p)->len++]=(kwchar)ch;
	((kBwcs*)p)->data[((kBwcs*)p)->len]=L'\0';
	return p;
}

K_INLINE kpointer k_bwcs_append_rep(kpointer p, kint ch, kint cnt)
{
	((kBwcs*)p)->len=(kint)k_wcsfll(((kBwcs*)p)->data, ((kBwcs*)p)->len, ((kBwcs*)p)->len+cnt, ch);
	((kBwcs*)p)->data[((kBwcs*)p)->len]=L'\0';
	return p;
}

K_INLINE kcham k_bwcs_is_empty(kconstpointer p)
{
	return ((const kBwcs*)p)->len==0;
}

K_INLINE kcham k_bwcs_is_have(kconstpointer p)
{
	return ((const kBwcs*)p)->len!=0;
}

K_INLINE size_t k_bwcs_hash(kconstpointer p)
{
	return k_wcshash(((const kBwcs*)p)->data);
}

K_INLINE kint k_bwcs_compare(kconstpointer p, const kwchar* s, kcham igcase)
{
	if (igcase)
		return k_wcsicmp(((const kBwcs*)p)->data, s);
	else
		return k_wcscmp(((const kBwcs*)p)->data, s);
}

K_INLINE kint k_bwcs_compare_bls(kconstpointer p1, kconstpointer p2, kcham igcase)
{
	if (igcase)
		return k_wcsicmp(((const kBwcs*)p1)->data, ((const kBwcs*)p2)->data);
	else
		return k_wcscmp(((const kBwcs*)p1)->data, ((const kBwcs*)p2)->data);
}

K_INLINE kint k_bwcs_compare_bls_length(kconstpointer p1, kconstpointer p2, kint len, kcham igcase)
{
	if (igcase)
		return k_wcsnicmp(((const kBwcs*)p1)->data, ((const kBwcs*)p2)->data, len);
	else
		return k_wcsncmp(((const kBwcs*)p1)->data, ((const kBwcs*)p2)->data, len);
}

K_INLINE void k_bwcs_format(kpointer p, kint size, const kwchar* fmt, ...)
{
	va_list va;
	va_start(va, fmt);
	((kBwcs*)p)->len=k_vsnwprintf(((kBwcs*)p)->data, size-1, fmt, va);
	va_end(va);
}

K_INLINE void k_bwcs_format_va(kpointer p, kint size, const kwchar* fmt, va_list va)
{
	((kBwcs*)p)->len=k_vsnwprintf(((kBwcs*)p)->data, size-1, fmt, va);
}

K_INLINE void k_bwcs_append_format(kpointer p, kint size, const kwchar* fmt, ...)
{
	va_list va;
	va_start(va, fmt);
	((kBwcs*)p)->len+=k_vsnwprintf(((kBwcs*)p)->data+((kBwcs*)p)->len, size-1-((kBwcs*)p)->len, fmt, va);
	va_end(va);
}

K_INLINE void k_bwcs_append_format_va(kpointer p, kint size, const kwchar* fmt, va_list va)
{
	((kBwcs*)p)->len+=k_vsnwprintf(((kBwcs*)p)->data+((kBwcs*)p)->len, size-1-((kBwcs*)p)->len, fmt, va);
}

K_INLINE kint k_bwcs_has_char(kconstpointer p, const kwchar* kwchars)
{
	kwchar* s=k_wcsbrk(((kBwcs*)p)->data, kwchars);
	return (s) ? (kint)(s-((kBwcs*)p)->data) : -1;
}

K_INLINE kint k_bwcs_find_char(kconstpointer p, int at, kwchar ch)
{
	kwchar* s=k_wcschr(((kBwcs*)p)->data+at, ch);
	return (s) ? (kint)(s-((kBwcs*)p)->data) : -1;
}

K_INLINE kcham k_bwcs_sub_bls(kpointer p, kconstpointer s, kint pos, kint len)
{
	k_return_value_if_fail(pos>=0, FALSE);
	k_return_value_if_fail(((const kBwcs*)s)->len>=pos, FALSE);

	if (len>0)
	{
		k_return_value_if_fail(((const kBwcs*)s)->len>=(pos+len), FALSE);
	}
	else
	{
		len=((const kBwcs*)s)->len-pos;
	}

	k_wcsmid(((kBwcs*)p)->data, ((const kBwcs*)s)->data, pos, len);
	((kBwcs*)p)->len=len;
	return TRUE;
}

K_INLINE void k_bwcs_upper(kpointer p)
{
	k_wcsupr(((kBwcs*)p)->data);
}

K_INLINE void k_bwcs_lower(kpointer p)
{
	k_wcslwr(((kBwcs*)p)->data);
}

K_INLINE void k_bwcs_trim(kpointer p)
{
	k_wcstrim(((kBwcs*)p)->data);
	((kBwcs*)p)->len=(kint)k_wcslen(((kBwcs*)p)->data);
}

K_INLINE void k_bwcs_trim_left(kpointer p)
{
	k_wcsltrim(((kBwcs*)p)->data);
	((kBwcs*)p)->len=(kint)k_wcslen(((kBwcs*)p)->data);
}

K_INLINE void k_bwcs_trim_right(kpointer p)
{
	k_wcsrtrim(((kBwcs*)p)->data);
	((kBwcs*)p)->len=(kint)k_wcslen(((kBwcs*)p)->data);
}

K_INLINE void k_bwcs_rem_chars(kpointer p, const kwchar* rmlist)
{
	((kBwcs*)p)->len=(kint)k_wcslen(k_wcsrem(((kBwcs*)p)->data, rmlist));
}

K_EXTERN_C_END





















#ifdef __cplusplus
//////////////////////////////////////////////////////////////////////////
// C++ container class





















//////////////////////////////////////////////////////////////////////////
// container iterator
namespace tpl
{
	namespace _iter
	{
		// array const iterator
		template <typename T>
		struct ArrayConstIterator
		{
			typedef ArrayConstIterator<T> this_type;
			typedef T value_type;

			value_type* item;

			ArrayConstIterator()
				: item(NULL)
			{
			}

			ArrayConstIterator(value_type* item)
				: item(item)
			{
			}

			ArrayConstIterator(const ArrayConstIterator& right)
				: item(right.item)
			{
			}

			ArrayConstIterator& operator=(const ArrayConstIterator& right)
			{
				item = right.item;
				return *this;
			}

			const value_type& operator*() const
			{
				return *item;
			}

			value_type const* operator->() const
			{
				return (&** this);
			}

			kssize_t operator-(const ArrayConstIterator& right) const
			{
				return item - right.item;
			}

			const value_type& operator[](ksize_t index) const
			{
				return (*(*this + index));
			}

			ArrayConstIterator& operator++()
			{
				++item;
				return *this;
			}

			ArrayConstIterator& operator--()
			{
				--item;
				return *this;
			}

			ArrayConstIterator operator++(int)
			{
				this_type t(*this);
				++*this;
				return t;
			}

			ArrayConstIterator operator--(int)
			{
				this_type t(*this);
				--*this;
				return t;
			}

			ArrayConstIterator& operator+=(ksize_t right)
			{
				item += right;
				return *this;
			}

			ArrayConstIterator& operator-=(ksize_t right)
			{
				item -= right;
				return *this;
			}

			ArrayConstIterator operator+(ksize_t right)
			{
				this_type t(this);
				return t += right;
			}

			ArrayConstIterator operator-(ksize_t right)
			{
				this_type t(this);
				return t -= right;
			}

			bool operator==(const ArrayConstIterator& right) const
			{
				return item == right.item;
			}

			bool operator!=(const ArrayConstIterator& right) const
			{
				return !operator==(right);
			}

			bool operator<(const ArrayConstIterator& right) const
			{
				return item < right.item;
			}

			bool operator>(const ArrayConstIterator& right) const
			{
				return right < *this;
			}

			bool operator<=(const ArrayConstIterator& right) const
			{
				return !(right > *this);
			}

			bool operator>=(const ArrayConstIterator& right) const
			{
				return !(*this < right);
			}
		};

		// array iterator
		template <typename T>
		struct ArrayIterator : public ArrayConstIterator<T>
		{
			typedef ArrayIterator<T> this_type;
			typedef ArrayConstIterator<T> super_type;
			typedef typename super_type::value_type value_type;

			ArrayIterator()
				: super_type()
			{
			}

			ArrayIterator(value_type* item)
				: super_type(item)
			{
			}

			ArrayIterator(const ArrayIterator& right)
				: super_type(right)
			{
			}

			value_type& operator*()
			{
				return *this->item;
			}

			value_type* operator->()
			{
				return (&** this);
			}

			kssize_t operator-(const super_type& right) const
			{
				return *(super_type*)this - right;
			}

			value_type& operator[](int index) const
			{
				return (*(*this + index));
			}

			ArrayIterator& operator++()
			{
				++(*(super_type*)this);
				return *this;
			}

			ArrayIterator& operator--()
			{
				--(*(super_type*)this);
				return *this;
			}

			ArrayIterator operator++(int)
			{
				this_type v(*this);
				++*this;
				return v;
			}

			ArrayIterator operator--(int)
			{
				this_type v(*this);
				--*this;
				return v;
			}

			ArrayIterator& operator+=(int right)
			{
				(*(super_type*)this) += right;
				return *this;
			}

			ArrayIterator& operator-=(int right)
			{
				(*(super_type*)this) -= right;
				return *this;
			}

			ArrayIterator operator+(int right)
			{
				this_type v(*this);
				return v += right;
			}

			ArrayIterator operator-(int right)
			{
				this_type v(*this);
				return v -= right;
			}
		};


		// list node
		template <typename T>
		struct LinkedListNode : public MemBase
		{
			typedef LinkedListNode<T> this_type;
			typedef T value_type;

			LinkedListNode* next;
			LinkedListNode* prev;
			value_type item;

			LinkedListNode(const value_type& item)
				: next(NULL), prev(NULL), item(item)
			{
			}
		};

		// list const iterator
		template <typename T>
		struct LinkedListConstIterator
		{
			typedef LinkedListConstIterator<T> this_type;
			typedef LinkedListNode<T> node_type;
			typedef T value_type;

			node_type* node;

			LinkedListConstIterator()
				: node(NULL)
			{
			}

			LinkedListConstIterator(node_type* node)
				: node(node)
			{
			}

			LinkedListConstIterator(const LinkedListConstIterator& right)
				: node(right.node)
			{
			}

			LinkedListConstIterator& operator=(const LinkedListConstIterator& right)
			{
				node = right.node;
				return *this;
			}

			const value_type& operator*() const
			{
				return node->item;
			}

			value_type const* operator->() const
			{
				return (&** this);
			}

			LinkedListConstIterator& operator++()
			{
				node = node->prev;
				return *this;
			}

			LinkedListConstIterator& operator--()
			{
				node = node->next;
				return *this;
			}

			LinkedListConstIterator operator++(int)
			{
				this_type v(*this);
				++*this;
				return v;
			}

			LinkedListConstIterator operator--(int)
			{
				this_type v(*this);
				--*this;
				return v;
			}

			bool operator==(const LinkedListConstIterator& right) const
			{
				return node == right.node;
			}

			bool operator!=(const LinkedListConstIterator& right) const
			{
				return !operator==(right);
			}
		};

		// list iterator
		template <typename T>
		struct LinkedListIterator : public LinkedListConstIterator<T>
		{
			typedef LinkedListIterator<T> this_type;
			typedef LinkedListConstIterator<T> super_type;
			typedef LinkedListNode<T> node_type;
			typedef typename super_type::value_type value_type;

			LinkedListIterator()
			{
			}

			LinkedListIterator(node_type* node)
				: super_type(node)
			{
			}

			LinkedListIterator(const LinkedListIterator& right)
				: super_type(right.node)
			{
			}

			value_type& operator*() const
			{
				return super_type::node->item;
			}

			value_type* operator->() const
			{
				return (&** this);
			}

			LinkedListIterator& operator++()
			{
				++(*(super_type*)this);
				return *this;
			}

			LinkedListIterator& operator--()
			{
				--(*(super_type*)this);
				return *this;
			}

			LinkedListIterator operator++(int)
			{
				this_type v(*this);
				++*this;
				return v;
			}

			LinkedListIterator operator--(int)
			{
				this_type v(*this);
				--*this;
				return v;
			}
		};


		// node list node
		template <typename T>
		struct NodeListNode : public MemBase
		{
			typedef NodeListNode<T> this_type;
			typedef T node_type;

			node_type* _node_next;
			node_type* _node_prev;
		};

		// node list const iterator
		template <typename T>
		struct NodeListConstIterator
		{
			typedef NodeListConstIterator<T> this_type;
			typedef T node_type;

			node_type* node;

			NodeListConstIterator()
				: node(NULL)
			{
			}

			NodeListConstIterator(node_type* node)
				: node(node)
			{
			}

			NodeListConstIterator(const NodeListConstIterator& right)
				: node(right.node)
			{
			}

			NodeListConstIterator& operator=(const NodeListConstIterator& right)
			{
				node = right.node; return *this;
			}

			const node_type& operator*() const
			{
				return *node;
			}

			node_type const* operator->() const
			{
				return (&** this);
			}

			NodeListConstIterator& operator++()
			{
				node = node->_node_prev;
				return *this;
			}

			NodeListConstIterator& operator--()
			{
				node = node->_node_next;
				return *this;
			}

			NodeListConstIterator operator++(int)
			{
				this_type v(*this);
				++*this;
				return v;
			}

			NodeListConstIterator operator--(int)
			{
				this_type v(*this);
				--*this;
				return v;
			}

			bool operator==(const NodeListConstIterator& right) const
			{
				return node == right.node;
			}

			bool operator!=(const NodeListConstIterator& right) const
			{
				return !operator==(right);
			}
		};

		// node list iterator
		template <typename T>
		struct NodeListIterator : public NodeListConstIterator<T>
		{
			typedef NodeListIterator<T> this_type;
			typedef NodeListConstIterator<T> super_type;
			typedef typename super_type::node_type node_type;

			NodeListIterator()
			{
			}

			NodeListIterator(node_type* node)
				: super_type(node)
			{
			}

			NodeListIterator(const NodeListIterator& right)
				: super_type(right.node)
			{
			}

			node_type& operator*()
			{
				return *super_type::node;
			}

			node_type* operator->()
			{
				return (&** this);
			}

			NodeListIterator& operator++()
			{
				++(*(super_type*)this);
				return *this;
			}

			NodeListIterator& operator--()
			{
				--(*(super_type*)this);
				return *this;
			}

			NodeListIterator operator++(int)
			{
				this_type v(*this);
				++*this;
				return v;
			}

			NodeListIterator operator--(int)
			{
				this_type v(*this);
				--*this;
				return v;
			}
		};


		// solo list node
		template <typename T>
		struct SoloListNode : public MemBase
		{
			typedef SoloListNode<T> this_type;
			typedef T value_type;

			SoloListNode* next;
			value_type item;

			SoloListNode(const value_type& item)
				: next(NULL), item(item)
			{
			}

			SoloListNode()
			{
			}
		};

		// solo list const iterator
		template <typename T>
		struct SoloListConstIterator
		{
			typedef SoloListConstIterator<T> this_type;
			typedef SoloListNode<T> node_type;
			typedef T value_type;

			node_type* node;

			SoloListConstIterator()
				: node(NULL)
			{
			}

			SoloListConstIterator(node_type* node)
				: node(node)
			{
			}

			SoloListConstIterator(const SoloListConstIterator& right)
				: node(right.node)
			{
			}

			SoloListConstIterator& operator=(const SoloListConstIterator& right)
			{
				node = right.node;
				return *this;
			}

			const value_type& operator*() const
			{
				return node->item;
			}

			const value_type& operator->() const
			{
				return (&** this);
			}

			SoloListConstIterator& operator++()
			{
				node = node->next;
				return *this;
			}

			SoloListConstIterator operator++(int)
			{
				this_type v(*this);
				++*this;
				return v;
			}

			bool operator==(const SoloListConstIterator& right) const
			{
				return node == right.node;
			}

			bool operator!=(const SoloListConstIterator& right) const
			{
				return !operator==(right);
			}

			operator bool() const
			{
				return node != NULL;
			}

			bool operator!() const
			{
				return node == NULL;
			}
		};

		// solo list iterator
		template <typename T>
		struct SoloListIterator : public SoloListConstIterator<T>
		{
			typedef SoloListIterator<T> this_type;
			typedef SoloListConstIterator<T> super_type;
			typedef SoloListNode<T> node_type;
			typedef typename super_type::value_type value_type;

			SoloListIterator()
			{
			}

			SoloListIterator(node_type* node)
				: super_type(node)
			{
			}

			SoloListIterator(const SoloListIterator& right)
				: super_type(right.node)
			{
			}

			value_type& operator*()
			{
				return super_type::node->item;
			}

			value_type& operator->() const
			{
				return (&** this);
			}

			SoloListIterator& operator++()
			{
				++(*(super_type*)this);
				return *this;
			}

			SoloListIterator operator++(int)
			{
				this_type v(*this);
				++*this;
				return v;
			}
		};


		// hash pair
		template <typename KEY, typename MAP>
		struct HashItem
		{
			typedef HashItem<KEY, MAP> this_type;
			typedef KEY key_type;
			typedef MAP map_type;

			key_type key;
			map_type map;

			HashItem()
				: key(key_type()), map(map_type())
			{
			}

			HashItem(const key_type& key, const map_type& map)
				: key(key), map(map)
			{
			}

			explicit HashItem(const key_type& key)
				: key(key), map(map_type())
			{
			}

			template <typename _K, typename _V> HashItem(const HashItem<_K, _V>& right)
				: key(right.key), map(right.map)
			{
			}
		};

		// hash node
		template <typename KEY, typename MAP>
		struct HashNode : public MemZero
		{
			typedef HashNode<KEY, MAP> this_type;
			typedef Pair<KEY, MAP> value_type;
			typedef KEY key_type;
			typedef MAP map_type;

			this_type* sib;
			this_type* next;
			this_type* prev;
			ksize_t hash;
			value_type value;

			HashNode()
			{
			}

			HashNode(ksize_t hash, const value_type& value)
				: sib(NULL), hash(hash), value(value)
			{
			}

			HashNode(ksize_t hash, const key_type& key, const map_type& map)
				: sib(NULL), hash(hash), value(key, map)
			{
			}

			HashNode(ksize_t hash, const key_type& key)
				: sib(NULL), hash(hash), value(key)
			{
			}

			explicit HashNode(ksize_t hash)
				: sib(NULL), hash(hash)
			{
			}
		};

		// hash const iterator
		template <typename KEY, typename MAP>
		struct HashConstIterator
		{
			typedef HashConstIterator<KEY, MAP> this_type;
			typedef HashNode<KEY, MAP> node_type;
			typedef typename node_type::value_type value_type;

			node_type* node;

			HashConstIterator()
				: node(NULL)
			{
			}

			HashConstIterator(node_type* node)
				: node(node)
			{
			}

			HashConstIterator(const HashConstIterator& right)
				: node(right.node)
			{
			}

			HashConstIterator& operator=(const HashConstIterator& right)
			{
				node = right.node;
				return *this;
			}

			const value_type& operator*() const
			{
				return node->value;
			}

			value_type const* operator->() const
			{
				return (&**this);
			}

			HashConstIterator& operator++()
			{
				node = node->prev;
				return *this;
			}

			HashConstIterator& operator--()
			{
				node = node->next;
				return *this;
			}

			HashConstIterator operator++(int)
			{
				this_type v(*this);
				++*this;
				return v;
			}

			HashConstIterator operator--(int)
			{
				this_type v(*this);
				--*this;
				return v;
			}

			bool operator==(const HashConstIterator& right) const
			{
				return node == right.node;
			}

			bool operator!=(const HashConstIterator& right) const
			{
				return !operator==(right);
			}
		};

		// hash iterator
		template <typename KEY, typename MAP>
		struct HashIterator : public HashConstIterator<KEY, MAP>
		{
			typedef HashIterator<KEY, MAP> this_type;
			typedef HashConstIterator<KEY, MAP> super_type;
			typedef HashNode<KEY, MAP> node_type;
			typedef typename node_type::value_type value_type;

			HashIterator()
			{
			}

			HashIterator(node_type* node)
				: super_type(node)
			{
			}

			HashIterator(const HashIterator& right)
				: super_type(right.node)
			{
			}

			value_type& operator*() const
			{
				return super_type::node->value;
			}

			value_type* operator->() const
			{
				return (&** this);
			}

			HashIterator& operator++()
			{
				++(*(super_type*)this);
				return *this;
			}

			HashIterator& operator--()
			{
				--(*(super_type*)this);
				return *this;
			}

			HashIterator operator++(int)
			{
				this_type v(*this);
				++*this;
				return v;
			}

			HashIterator operator--(int)
			{
				this_type v(*this);
				--*this;
				return v;
			}
		};


		// mukum node
		template <typename KEY, typename MAP>
		struct MukumNode : public MemBase
		{
			typedef MukumNode<KEY, MAP> this_type;
			typedef Pair<KEY, MAP> value_type;
			typedef KEY key_type;
			typedef MAP map_type;

			this_type* sib;
			ksize_t hash;
			value_type value;

			MukumNode()
			{
			}

			MukumNode(ksize_t hash, const value_type& value)
				: sib(NULL), hash(hash), value(value)
			{
			}

			MukumNode(ksize_t hash, const key_type& key, const map_type& map)
				: sib(NULL), hash(hash), value(key, map)
			{
			}

			MukumNode(ksize_t hash, const key_type& key)
				: sib(NULL), hash(hash), value(key)
			{
			}

			MukumNode(ksize_t hash)
				: sib(NULL), hash(hash)
			{
			}
		};

		// mukum const iterator
		template <typename KEY, typename MAP>
		struct MukumConstIterator
		{
			typedef MukumConstIterator<KEY, MAP> this_type;
			typedef MukumNode<KEY, MAP> node_type;
			typedef typename node_type::value_type value_type;

			node_type* node;

			MukumConstIterator()
				: node(NULL)
			{
			}

			MukumConstIterator(node_type* node)
				: node(node)
			{
			}

			MukumConstIterator(const MukumConstIterator& right)
				: node(right.node)
			{
			}

			MukumConstIterator& operator=(const MukumConstIterator& right)
			{
				node = right.node;
				return *this;
			}

			const value_type& operator*() const
			{
				return node->value;
			}

			value_type const* operator->() const
			{
				return (&** this);
			}

			bool operator==(const MukumConstIterator& right) const
			{
				return node == right.node;
			}

			bool operator!=(const MukumConstIterator& right) const
			{
				return !operator==(right);
			}
		};

		// mukum iterator
		template <typename KEY, typename MAP>
		struct MukumIterator : public MukumConstIterator<KEY, MAP>
		{
			typedef MukumIterator<KEY, MAP> this_type;
			typedef MukumConstIterator<KEY, MAP> super_type;
			typedef MukumNode<KEY, MAP> node_type;
			typedef typename node_type::value_type value_type;

			MukumIterator()
			{
			}

			MukumIterator(node_type* node)
				: super_type(node)
			{
			}

			MukumIterator(const MukumIterator& right)
				: super_type(right.node)
			{
			}

			value_type& operator*() const
			{
				return super_type::node->value;
			}

			value_type* operator->() const
			{
				return (&** this);
			}
		};
	}   // tpl::_iter
}	// tpl






















//////////////////////////////////////////////////////////////////////////
// containers
namespace tpl
{
	// array
	template <typename T>
	class Array : public MemBase
	{
		KCH_NOEC(Array);

	public:
		typedef Array<T> this_type;
		typedef T value_type;
		typedef _iter::ArrayConstIterator<T> ConstIterator;
		typedef _iter::ArrayIterator<T> Iterator;

		value_type* _data;
		ksize_t _count;

		Array()
			: _data(NULL), _count(0)
		{
		}

		explicit Array(ksize_t count)
		{
			if (count == 0)
			{
				_data = NULL;
				_count = 0;
			}
			else
			{
				_data = k_new(count, value_type);
				_count = count;

				MemTrait::ConstructN(_data, count);
			}
		}

		template <typename ITER>
		Array(ITER begin, ITER end)
		{
			ksize_t size = end - begin;

			if (size == 0)
			{
				_data = NULL;
				_count = 0;
			}
			else
			{
				_data = k_new(size, value_type);
				_count = size;

				MemTrait::Construct(_data, begin, end);
			}
		}

		~Array()
		{
			if (_count!=0)
			{
				MemTrait::DestructN(_data, _count);
				k_delete(_data);
			}
		}

		const T& operator[](kint index) const
		{
			return *(_data + index);
		}

		T& operator[](kint index)
		{
			return *(_data + index);
		}

		bool IsEmpty() const
		{
			return _count == 0;
		}

		bool IsHave() const
		{
			return _count != 0;
		}

		kint Count() const
		{
			return (kint)_count;
		}

		const value_type* Data() const
		{
			return _data;
		}

		value_type* Data()
		{
			return _data;
		}

		ksize_t Stride() const
		{
			return sizeof(T);
		}

		void Resize(kint size)
		{
			if (_count != 0)
				MemTrait::DestructN(_data, _count);

			_data = k_renew(_data, size, value_type);
			_count = size;

			MemTrait::ConstructN(_data, size);
		}

		// need to impls
		// insert

		kint Contains(const value_type& item, kint start, kint count) const
		{
			kint last = start + count;
			if (last > _count)
				last = _count;

			for (ksize_t i = start; i < last; i++)
			{
				if (_data[i] == item)
					return (kint)i;
			}

			return -1;
		}

		kint Contains(const value_type& item, kint start) const
		{
			return Contains(item, start, _count - start);
		}

		kint Contains(const value_type& item) const
		{
			return Contains(item, 0, _count);
		}

		bool RemoveAt(kint index)
		{
			if (index < 0)
				return false;

			if (index >= _count)
				return false;

			value_type* p = _data + index;
			MemTrait::Destruct(p);
			memmove(p, p + 1, sizeof(value_type) * (_count - (index + 1)));

			MemTrait::Construct(_data - _count - 1);

			return true;
		}

		bool Remove(const value_type& item)
		{
			kint n = Contains(item);
			return RemoveAt(n);
		}

		Iterator Remove(Iterator it)
		{
			MemTrait::Destruct(&(*it));
			memmove(it.item, it.item + 1, sizeof(value_type) * ((_data + _count) - it.item));

			MemTrait::Construct(_data - _count - 1);

			return it;
		}

		void Fill(const value_type& item)
		{
			MemTrait::DestructN(_data, _count);
			MemTrait::ConstructR(_data, _count, item);
		}

		void FillData(value_type* buf, kint size)
		{
			if (size > (kint)_count)
				size = (kint)_count;

			memcpy(_data, buf, sizeof(value_type)* size);
		}

		void Nullify()
		{
			// for avoid delete data
			_data = NULL;
			_count = 0;
		}

		void Swap(value_type*& p, kint& count)
		{
			tpl::Swap(_data, p);
			tpl::SwapL(_count, count);
		}

		void Swap(this_type& right)
		{
			tpl::Swap(_data, right._data);
			tpl::Swap(_count, right._count);
		}

		Iterator Begin() const
		{
			return Iterator(_data);
		}

		Iterator End() const
		{
			return Iterator(_data + _count);
		}

		ConstIterator ConstBegin() const
		{
			return ConstIterator(_data);
		}

		ConstIterator ConstEnd() const
		{
			return ConstIterator(_data + _count);
		}

		Iterator begin() const
		{
			return Iterator(_data);
		}

		Iterator end() const
		{
			return Iterator(_data + _count);
		}

		ConstIterator cbegin() const
		{
			return ConstIterator(_data);
		}

		ConstIterator cend() const
		{
			return ConstIterator(_data + _count);
		}
	};

	// sequence array
	template <typename T>
	class SeqArray : public MemBase
	{
		KCH_NOEC(SeqArray);

	public:
		typedef SeqArray<T> this_type;
		typedef T value_type;
		typedef _iter::ArrayConstIterator<T> ConstIterator;
		typedef _iter::ArrayIterator<T> Iterator;

		value_type* _data;
		ksize_t _count;
		ksize_t _capa;

		SeqArray()
			: _data(NULL), _count(0), _capa(0)
		{
		}

		explicit SeqArray(ksize_t capacity)
			: _data(NULL), _count(0), _capa(0)
		{
			_InternalExpand((ksize_t)capacity);
		}

		SeqArray(ksize_t count, const value_type& value)
			: _data(NULL), _count(0), _capa(0)
		{
			if (count > 0)
			{
				_InternalExpand(count);
				MemTrait::ConstructN(_data, count, value);
				_count = count;
			}
		}

		template <typename ITER>
		SeqArray(ITER begin, ITER end)
			: _data(NULL), _count(0), _capa(0)
		{
			ksize_t size = end - begin;

			if (size > 0)
			{
				_InternalExpand(size);
				MemTrait::Construct(_data, begin, end);
				_count = size;
			}
		}

#if _SB_CPP11_MOVE_
		SeqArray(SeqArray&& right)
		{
			_data = right._data;
			_count = right._count;
			_capa = right._capa;

			right._data = NULL;
			right._count = 0;
			right._capa = 0;
		}
#endif

		~SeqArray()
		{
			MemTrait::DestructN(_data, _count);
			k_delete(_data);
		}

		const value_type& operator[](kint index) const
		{
			return _data[index];
		}

		value_type& operator[](kint index)
		{
			return _data[index];
		}

		bool IsEmpty() const
		{
			return _count == 0;
		}

		bool IsHave() const
		{
			return _count != 0;
		}

		kint Capacity() const
		{
			return (kint)_capa;
		}

		kint Count() const
		{
			return (kint)_count;
		}

		const value_type* Data() const
		{
			return _data;
		}

		value_type* Data()
		{
			return _data;
		}

		ksize_t Stride() const
		{
			return sizeof(T);
		}

		void Reserve(kint count)
		{
			_InternalExpand(count);

			if ((ksize_t)count >= _count)
				MemTrait::ConstructR(_data, _count, (ksize_t)count);

			_count = (ksize_t)count;
		}

		void Add(const value_type& item)
		{
			if (_count >= _capa)
				_InternalExpand(_capa + 1);

			MemTrait::Construct(&_data[_count++], item);
		}

		bool Insert(kint index, const value_type& item)
		{
			if ((ksize_t)index > _count)
				return false;

			if (_count >= _capa)
				_InternalExpand(_capa + 1);

			memmove(&_data[index + 1], &_data[index], sizeof(value_type)* (_count - (ksize_t)index));
			MemTrait::Construct(&_data[index], item);

			_count++;
			return true;
		}

		kint Contains(const value_type& item, kint start, kint count) const
		{
			ksize_t last;

			if (count <= 0 || (last = start + count) >= _count)
				return -1;

			for (ksize_t i = (ksize_t)start; i < last; i++)
			{
				if (_data[i] == item)
					return (kint)i;
			}

			return -1;
		}

		kint Contains(const value_type& item, kint start) const
		{
			return Contains(item, start, _count - (ksize_t)start);
		}

		kint Contains(const value_type& item) const
		{
			return Contains(item, 0, (kint)_count);
		}

		bool RemoveAt(ksize_t index)
		{
			if (index >= _count)
				return false;
			else
			{
				MemTrait::Destruct(&_data[index]);
				memmove(&_data[index], &_data[index + 1], sizeof(value_type)* (_count - (index + 1)));

				_count--;
				return true;
			}
		}

		bool Remove(const value_type& item)
		{
			kssize_t n = Contains(item);
			return RemoveAt(n);
		}

		Iterator Remove(Iterator it)
		{
			MemTrait::Destruct(&(*it));
			memmove(it.item, it.item + 1, sizeof(value_type)* (&_data[_count] - it.item));

			_count--;
			return it;
		}

		void Clear()
		{
			MemTrait::DestructN(_data, _count);
			_count = 0;
		}

		Iterator Begin()
		{
			return Iterator(_data);
		}

		Iterator End()
		{
			return _count ? Iterator(&_data[_count]) : Iterator();
		}

		Iterator First()
		{
			return _count ? Iterator(&_data[0]) : Iterator();
		}

		Iterator Last()
		{
			return _count ? Iterator(&_data[_count - 1]) : Iterator();
		}

		ConstIterator ConstBegin() const
		{
			return ConstIterator(_data);
		}

		ConstIterator ConstEnd() const
		{
			return _count ? ConstIterator(&_data[_count]) : ConstIterator();
		}

		ConstIterator ConstFirst() const
		{
			return _count ? ConstIterator(&_data[0]) : ConstIterator();
		}

		ConstIterator ConstLast() const
		{
			return _count ? ConstIterator(&_data[_count - 1]) : ConstIterator();
		}

		Iterator begin()
		{
			return Iterator(_data);
		}

		Iterator end()
		{
			return _count ? Iterator(&_data[_count]) : Iterator();
		}

		Iterator first()
		{
			return _count ? Iterator(&_data[0]) : Iterator();
		}

		Iterator last()
		{
			return _count ? Iterator(&_data[_count - 1]) : Iterator();
		}

		ConstIterator cbegin() const
		{
			return ConstIterator(_data);
		}

		ConstIterator cend() const
		{
			return _count ? ConstIterator(&_data[_count]) : ConstIterator();
		}

		ConstIterator cfirst() const
		{
			return _count ? ConstIterator(&_data[0]) : ConstIterator();
		}

		ConstIterator clast() const
		{
			return _count ? ConstIterator(&_data[_count - 1]) : ConstIterator();
		}

	protected:
		void _InternalExpand(kint count)
		{
			if (_count > (ksize_t)count)
				MemTrait::DestructR(_data, (ksize_t)count, _count);
			else if ((ksize_t)count > _capa)
			{
				_capa = _capa + _capa / 2;

				if (_capa < (ksize_t)count)
					_capa = (ksize_t)count;

				_data = k_renew(_data, _capa, value_type);
			}
		}
	};

	// vector array
	template <typename T>
	class VecArray : public MemBase
	{
		KCH_NOEC(VecArray);

	public:
		typedef VecArray<T> this_type;
		typedef T value_type;
		typedef _iter::ArrayConstIterator<T> ConstIterator;
		typedef _iter::ArrayIterator<T> Iterator;

		value_type* _frst;
		value_type* _last;
		value_type* _end;

		VecArray()
			: _frst(NULL), _last(NULL), _end(NULL)
		{
		}

		explicit VecArray(ksize_t capacity)
		{
			if (capacity <= 0)
			{
				_frst = _last = _end = NULL;
			}
			else
			{
				_frst = k_new(capacity, value_type);
				_last = _frst;
				_end = _frst + capacity;
			}
		}

		template <typename ITER>
		VecArray(ITER begin, ITER end)
		{
			ksize_t size = end - begin;

			if (size == 0)
				_frst = _last = _end = NULL;
			else
			{
				_frst = k_new(size, value_type);
				_last = _end = _frst + size;

				MemTrait::Construct(_frst, begin, end);
			}
		}

		/*
		explicit VecArray(const VecArray& right)
		{
			ksize_t size = right.Count();

			if (size == 0)
			{
				_frst = _last = _end = NULL;
			}
			else
			{
				_frst = k_new(size, value_type);
				_last = _end = _frst + size;

				MemTrait::Construct(_frst, right._frst, right._last);
			}
		}
		*/

		~VecArray()
		{
			MemTrait::Destruct(_frst, _last);
			k_delete(_frst);
		}

		const T& operator[](kint index) const
		{
			return *(_frst + index);
		}

		T& operator[](kint index)
		{
			return *(_frst + index);
		}

		bool IsEmpty() const
		{
			return _frst == _last;
		}

		bool IsHave() const
		{
			return _frst != _last;
		}

		kint Capacity() const
		{
			return (kint)(_end - _frst);
		}

		kint Count() const
		{
			return (kint)(_last - _frst);
		}

		const value_type* Data() const
		{
			return _frst;
		}

		value_type* Data()
		{
			return _frst;
		}

		ksize_t Stride() const
		{
			return sizeof(T);
		}

		void Reserve(kint reservecount)
		{
			ksize_t count = (ksize_t)reservecount;
			ksize_t capa = Capacity();
			ksize_t cnt = Count();

			if (capa < count)
			{
				capa = count;
				_frst = k_renew(_frst, capa, value_type);
				_last = _frst + capa;
				_end = _frst + capa;
				MemTrait::ConstructR(_frst, cnt, capa);
			}
			else if (count < cnt)
			{
				MemTrait::DestructR(_frst, count, cnt);
				_last = _frst + count;
			}
			else
			{
				MemTrait::ConstructR(_frst, cnt, count);
				_last = _frst + count;
			}
		}

		void Add(const value_type& item)
		{
			if (_end <= _last)
			{
				ksize_t capa = Capacity();
				ksize_t cnt = Count();
				capa = capa + capa / 2;

				if (capa <= cnt)
					capa = cnt + 1;

				_frst = k_renew(_frst, capa, value_type);
				_last = _frst + cnt;
				_end = _frst + capa;
			}

			MemTrait::Construct(_last++, item);
		}

		bool Insert(kint index, const value_type& item)
		{
			value_type* tmp = _frst + index;

			if (tmp > _last)
				return false;

			if (_end <= _last)
			{
				ksize_t capa = Capacity();
				ksize_t cnt = Count();
				capa = capa + capa / 2;

				if (capa <= cnt)
					capa = cnt + 1;

				_frst = k_renew(_frst, capa, value_type);
				_last = _frst + cnt;
				_end = _frst + capa;
				tmp = _frst + index;
			}

			if (tmp != _last)
				memmove(tmp + 1, tmp, sizeof(value_type)* (_last - tmp));

			MemTrait::Construct(tmp, item);
			_last++;

			return true;
		}

		kint Contains(const value_type& item, kint start, kint count) const
		{
			ksize_t cnt = Count();
			ksize_t tmp;

			if (count == 0 || (tmp = start + count) > cnt)
				return -1;

			value_type* tend = _frst + tmp;

			for (value_type* p = _frst + start; p != tend; ++p)
			{
				if (*p == item)
					return (int)(p - _frst);
			}

			return -1;
		}

		kint Contains(const value_type& item, kint start) const
		{
			return Contains(item, start, Count() - start);
		}

		kint Contains(const value_type& item) const
		{
			return Contains(item, 0, Count());
		}

		bool RemoveAt(kint index)
		{
			if (index < 0)
				return false;

			kint cnt = Count();

			if (index >= cnt)
				return false;

			value_type* p = _frst + index;
			MemTrait::Destruct(p);
			memmove(p, p + 1, sizeof(value_type)* (cnt - (index + 1)));

			--_last;
			return true;
		}

		bool Remove(const value_type& item)
		{
			kssize_t n = Contains(item);
			return RemoveAt(n);
		}

		Iterator Remove(Iterator it)
		{
			MemTrait::Destruct(&(*it));
			memmove(it.item, it.item + 1, sizeof(value_type)* (_last - it.item));

			_last--;
			return it;
		}

		void Clear()
		{
			if (_last != _frst)
			{
				MemTrait::Destruct(_frst, _last);
				_last = _frst;
			}
		}

		void Fill(const value_type& item)
		{
			MemTrait::Destruct(_frst, _last);
			MemTrait::ConstructF(_frst, _last, item);
		}

		Iterator Begin() const
		{
			return Iterator(_frst);
		}

		Iterator End() const
		{
			return Iterator(_last);
		}

		Iterator First() const
		{
			return Iterator(_frst);
		}

		Iterator Last() const
		{
			return Iterator(_last - 1);
		}

		ConstIterator ConstBegin() const
		{
			return ConstIterator(_frst);
		}

		ConstIterator ConstEnd() const
		{
			return ConstIterator(_last);
		}

		ConstIterator ConstFirst() const
		{
			return ConstIterator(_frst);
		}

		ConstIterator ConstLast() const
		{
			return ConstIterator(_last - 1);
		}

		Iterator begin()
		{
			return Iterator(_frst);
		}

		Iterator end()
		{
			return Iterator(_last);
		}

		Iterator first()
		{
			return Iterator(_frst);
		}

		Iterator last()
		{
			return Iterator(_last - 1);
		}

		ConstIterator cbegin() const
		{
			return ConstIterator(_frst);
		}

		ConstIterator cend() const
		{
			return ConstIterator(_last);
		}

		ConstIterator cfirst() const
		{
			return ConstIterator(_frst);
		}

		ConstIterator clast() const
		{
			return ConstIterator(_last - 1);
		}
	};

	// slice array
	template <typename T>
	class SliceArray : public MemBase
	{
		KCH_NOEC(SliceArray);

	public:
		typedef SliceArray<T> this_type;
		typedef T value_type;
		typedef _iter::ArrayConstIterator<T> ConstIterator;
		typedef _iter::ArrayIterator<T> Iterator;

		value_type* _data;
		ksize_t _max;
		ksize_t _count;

		SliceArray()
			: _data(NULL), _max(0), _count(0)
		{
		}

		explicit SliceArray(ksize_t max)
		{
			_data = max > 0 ? k_new(max, value_type) : NULL;
			_max = max;
			_count = 0;
		}

		~SliceArray()
		{
			MemTrait::DestructN(_data, _count);
			k_delete(_data);
		}

		const value_type& operator[](kint index) const
		{
			return _data[index];
		}

		value_type& operator[](kint index)
		{
			return _data[index];
		}

		bool IsEmpty() const
		{
			return _count == 0;
		}

		bool IsHave() const
		{
			return _count != 0;
		}

		kint Maximum() const
		{
			return (kint)_max;
		}

		kint Count() const
		{
			return (kint)_count;
		}

		const value_type* Data() const
		{
			return _data;
		}

		value_type* Data()
		{
			return _data;
		}

		ksize_t Stride() const
		{
			return sizeof(T);
		}

		bool Push(const value_type& item)
		{
			if (_count == _max)
				return false;
			else
			{
				MemTrait::Construct(&_data[_count++], item);
				return true;
			}
		}

		bool Pop(value_type& ret)
		{
			if (_count == 0)
				return false;

			MemTrait::Construct(&ret, _data[0]);
			MemTrait::Destruct(&_data[0]);

			if (_count == 1)
				_count = 0;
			else
			{
				_count--;
				MemTrait::Construct(&_data[0], _data[_count]);	// move
				MemTrait::Destruct(&_data[_count]);
			}

			return true;
		}

		bool Pop()
		{
			if (_count == 0)
				return false;

			MemTrait::Destruct(&_data[0]);

			if (_count == 1)
				_count = 0;
			else
			{
				_count--;
				MemTrait::Construct(&_data[0], _data[_count]);	// move
				MemTrait::Destruct(&_data[_count]);
			}

			return true;
		}

		void Clear()
		{
			MemTrait::DestructN(_data, _count);
			_count = 0;
		}

		void Reserve(kint size)
		{
			ksize_t newmax = (ksize_t)size;

			if (_count > newmax)
			{
				// delete over count
				MemTrait::DestructR(_data, newmax, _count);
				_count = newmax;
			}

			_data = k_renew(_data, newmax, value_type);
			_max = newmax;
		}

		void Disable()
		{
			_max = _count;
		}

		template <typename F>
		void ForEach(F fn2, kpointer data) const
		{
			ksize_t cnt = _count;

			for (ksize_t i = 0; i < cnt; i++)
				fn2(data, _data[i]);
		}

		template <typename F>
		void LoopEach(F fn1) const
		{
			ksize_t cnt = _count;

			for (ksize_t i = 0; i < cnt; i++)
				fn1(_data[i]);
		}

		Iterator Begin()
		{
			return Iterator(_data);
		}

		Iterator End()
		{
			return Iterator(&_data[_count]);
		}

		ConstIterator ConstBegin() const
		{
			return ConstIterator(_data);
		}

		ConstIterator ConstEnd() const
		{
			return ConstIterator(&_data[_count]);
		}

		Iterator begin()
		{
			return Iterator(_data);
		}

		Iterator end()
		{
			return Iterator(&_data[_count]);
		}

		ConstIterator cbegin() const
		{
			return ConstIterator(_data);
		}

		ConstIterator cend() const
		{
			return ConstIterator(&_data[_count]);
		}
	};

	// list
	template <typename T>
	class LinkedList : public MemBase
	{
		KCH_NOEC(LinkedList);

	public:
		typedef LinkedList<T> this_type;
		typedef T value_type;
		typedef _iter::LinkedListNode<T> node_type;
		typedef _iter::LinkedListConstIterator<T> ConstIterator;
		typedef _iter::LinkedListIterator<T> Iterator;

		node_type* _frst;
		node_type* _last;
		ksize_t _count;

		LinkedList()
			: _frst(NULL), _last(NULL), _count(0)
		{
		}

		template <typename ITER>
		LinkedList(ITER begin, ITER end)
			: _frst(NULL), _last(NULL), _count(0)
		{
			for (ITER it = begin; it != end; ++it)
				Append(*it);
		}

#if _SB_CPP11_MOVE_
		LinkedList(LinkedList&& right)
		{
			_frst = right._frst;
			_last = right._last;
			_count = right._count;

			right._frst = NULL;
			right._last = NULL;
			right._count = 0;
		}
#endif

		~LinkedList()
		{
			node_type* node;
			node_type* next;

			for (node = _frst; node; node = next)
			{
				next = node->next;
				delete node;
			}
		}

		kint Count() const
		{
			return (kint)_count;
		}

		bool IsEmpty() const
		{
			return _count == 0;
		}

		bool IsHave() const
		{
			return _count != 0;
		}

		void Append(const value_type& item)
		{
			node_type* node = new node_type(item);

			if (_frst)
				_frst->prev = node;
			else
				_last = node;

			node->next = _frst;

			_frst = node;
			_count++;
		}

		void Prepend(const value_type& item)
		{
			node_type* node = new node_type(item);

			if (_last)
				_last->next = node;
			else
				_frst = node;

			node->prev = _last;

			_last = node;
			_count++;
		}

		kint Contains(const value_type& item) const
		{
			node_type* node;
			ksize_t n;

			for (node = _frst, n = 0; node; node = node->next, n++)
			{
				if (node->item == item)
					return n;
			}

			return -1;
		}

		bool Remove(const value_type& item)
		{
			for (node_type* node = _frst; node; node = node->next)
			{
				if (node->item == item)
				{
					EraseNode(node);
					return true;
				}
			}

			return false;
		}

		Iterator Remove(Iterator it)
		{
			node_type* node = it.node;

			if (node)
			{
				++it;
				EraseNode(node);
			}

			return it;
		}

		void RemoveFirst()
		{
			EraseNode(_last);
		}

		void RemoveLast()
		{
			EraseNode(_frst);
		}

		void Clear()
		{
			node_type* node;
			node_type* next;

			for (node = _frst; node; node = next)
			{
				next = node->next;
				delete node;
			}

			_frst = _last = NULL;
			_count = 0;
		}

		void EraseNode(node_type* node)
		{
			if (node->next)
				node->next->prev = node->prev;
			else
			{
				k_assert_eq(_last, node);
				_last = node->prev;
			}

			if (node->prev)
				node->prev->next = node->next;
			else
			{
				k_assert_eq(_frst, node);
				_frst = node->next;
			}

			_count--;

			delete node;
		}

		Iterator First()
		{
			return Iterator(_last);
		}

		Iterator Last()
		{
			return Iterator(_frst);
		}

		Iterator Begin()
		{
			return Iterator(_last);
		}

		Iterator End()
		{
			return Iterator(NULL);
		}

		ConstIterator ConstFirst() const
		{
			return ConstIterator(_last);
		}

		ConstIterator ConstLast() const
		{
			return ConstIterator(_frst);
		}

		ConstIterator ConstBegin() const
		{
			return ConstIterator(_last);
		}

		ConstIterator ConstEnd() const
		{
			return ConstIterator(NULL);
		}

		Iterator first()
		{
			return Iterator(_last);
		}

		Iterator last()
		{
			return Iterator(_frst);
		}

		Iterator begin()
		{
			return Iterator(_last);
		}

		Iterator end()
		{
			return Iterator(NULL);
		}

		ConstIterator cfirst() const
		{
			return ConstIterator(_last);
		}

		ConstIterator clast() const
		{
			return ConstIterator(_frst);
		}

		ConstIterator cbegin() const
		{
			return ConstIterator(_last);
		}

		ConstIterator cend() const
		{
			return ConstIterator(NULL);
		}
	};

	// node
	template <typename T>
	class NodeList : public MemBase
	{
	public:
		typedef NodeList<T> this_type;
		typedef T node_type;
		typedef _iter::NodeListNode<T> parent_node_type;
		typedef _iter::NodeListConstIterator<T> ConstIterator;
		typedef _iter::NodeListIterator<T> Iterator;
		typedef _iter::NodeListNode<T> Node;

		node_type*      _frst;
		node_type*      _last;
		ksize_t			_count;

		NodeList()
			: _frst(NULL), _last(NULL), _count(0)
		{
		}

		~NodeList()
		{
			node_type* node;
			node_type* next;

			for (node = _frst; node; node = next)
			{
				next = node->_node_next;
				delete node;
			}
		}

		kint Count() const
		{
			return (kint)_count;
		}

		bool IsEmpty() const
		{
			return _count == 0;
		}

		bool IsHave() const
		{
			return _count != 0;
		}

		void Append(node_type* node)
		{
			if (_frst)
				_frst->_node_prev = node;
			else
				_last = node;

			node->_node_next = _frst;
			node->_node_prev = NULL;

			_frst = node;
			_count++;
		}

		void Prepend(node_type* node)
		{
			if (_last)
				_last->_node_next = node;
			else
				_frst = node;

			node->_node_next = NULL;
			node->_node_prev = _last;

			_last = node;
			_count++;
		}

		kint Contains(node_type* dest) const
		{
			node_type* node;
			ksize_t n;

			for (node = _frst, n = 0; node; node = node->_node_next, n++)
			{
				if (node == dest)
					return n;
			}

			return -1;
		}

		void Remove(node_type* node)
		{
			if (node)
				EraseNode(node);
		}

		Iterator Remove(Iterator it)
		{
			node_type* node = it.node;

			if (node)
			{
				++it;
				EraseNode(node);
			}

			return it;
		}

		void RemoveFirst()
		{
			EraseNode(_last);
		}

		void RemoveLast()
		{
			EraseNode(_frst);
		}

		void Clear()
		{
			node_type* node;
			node_type* next;

			for (node = _frst; node; node = next)
			{
				next = node->_node_next;
				delete node;
			}

			_frst = _last = NULL;
			_count = 0;
		}

		void EraseNode(node_type* node)
		{
			if (node->_node_next)
				node->_node_next->_node_prev = node->_node_prev;
			else
			{
				k_assert_eq(_last, node);
				_last = node->_node_prev;
			}

			if (node->_node_prev)
				node->_node_prev->_node_next = node->_node_next;
			else
			{
				k_assert_eq(_frst, node);
				_frst = node->_node_next;
			}

			_count--;
			delete node;
		}

		void Unlink(node_type* node)
		{
			if (node->_node_next)
				node->_node_next->_node_prev = node->_node_prev;
			else
			{
				k_assert_eq(_last, node);
				_last = node->_node_prev;
			}

			if (node->_node_prev)
				node->_node_prev->_node_next = node->_node_next;
			else
			{
				k_assert_eq(_frst, node);
				_frst = node->_node_next;
			}

			_count--;
			node->_node_next = node->_node_prev = NULL;
		}

		Iterator First()
		{
			return Iterator(_last);
		}

		Iterator Last()
		{
			return Iterator(_frst);
		}

		Iterator Begin()
		{
			return Iterator(_last);
		}

		Iterator End()
		{
			return Iterator(NULL);
		}

		ConstIterator ConstFirst() const
		{
			return ConstIterator(_last);
		}

		ConstIterator ConstLast() const
		{
			return ConstIterator(_frst);
		}

		ConstIterator ConstBegin() const
		{
			return ConstIterator(_last);
		}

		ConstIterator ConstEnd() const
		{
			return ConstIterator(NULL);
		}

		Iterator first()
		{
			return Iterator(_last);
		}

		Iterator last()
		{
			return Iterator(_frst);
		}

		Iterator begin()
		{
			return Iterator(_last);
		}

		Iterator end()
		{
			return Iterator(NULL);
		}

		ConstIterator cfirst() const
		{
			return ConstIterator(_last);
		}

		ConstIterator clast() const
		{
			return ConstIterator(_frst);
		}

		ConstIterator cbegin() const
		{
			return ConstIterator(_last);
		}

		ConstIterator cend() const
		{
			return ConstIterator(NULL);
		}
	};

	// single list
	template <typename T>
	class SoloList : public MemBase
	{
		KCH_NOEC(SoloList);

	public:
		typedef SoloList<T> this_type;
		typedef T value_type;
		typedef _iter::SoloListNode<T> node_type;
		typedef _iter::SoloListConstIterator<T> ConstIterator;
		typedef _iter::SoloListIterator<T> Iterator;

		node_type*      _node;

		SoloList()
			: _node(NULL)
		{
		}

		template <typename ITER>
		SoloList(ITER begin, ITER end)
		{
#if 0
			for (ITER it = begin; it != end; ++it)
				Prepend(*it);
#else
			ITER it = end - 1;
			do Prepend(*it); while (it-- != begin);
#endif
		}

		~SoloList()
		{
			node_type* node;
			node_type* next;

			for (node = _node; node; node = next)
			{
				next = node->next;
				delete node;
			}
		}

		bool IsEmpty() const
		{
			return _node == NULL;
		}

		bool IsHave() const
		{
			return _node != NULL;
		}

		void Append(const value_type& item)
		{
			node_type* node = new node_type(item);

			if (!_node)
				_node = node;
			else
			{
				node_type* last = LastNode();
				last->next = node;
			}
		}

		Iterator Append()
		{
			node_type* node = new node_type();

			if (!_node)
				_node = node;
			else
			{
				node_type* last = LastNode();
				last->next = node;
			}

			return Iterator(node);
		}

		void Prepend(const value_type& item)
		{
			node_type* node = new node_type(item);

			node->next = _node;
			_node = node;
		}

		Iterator Prepend()
		{
			node_type* node = new node_type();

			node->next = _node;
			_node = node;

			return Iterator(node);
		}

		bool Remove(const value_type& item)
		{
			node_type* node = _node;
			node_type* prev = NULL;

			while (node)
			{
				if (node->item == item)
				{
					if (prev)
						prev->next = node->next;
					else
						_node = node->next;

					delete node;

					return true;
				}

				prev = node;
				node = prev->next;
			}

			return false;
		}

		kint RemoveAll(const value_type& item)
		{
			node_type* node = _node;
			node_type* prev = NULL;
			node_type* next;
			kint count = 0;

			while (node)
			{
				if (node->item == item)
				{
					next = node->next;

					if (prev)
						prev->next = next;
					else
						_node = next;

					delete node;

					count++;
					node = next;
				}
				else
				{
					prev = node;
					node = prev->next;
				}
			}

			return count;
		}

		Iterator Remove(Iterator it)
		{
			node_type* node = it.node;

			if (node)
			{
				++it;
				Remove(node->item);
			}

			return it;
		}

		void Clear()
		{
			node_type* node;
			node_type* next;

			for (node = _node; node; node = next)
			{
				next = node->next;
				delete node;
			}

			_node = NULL;
		}

		Iterator At(ksize_t nth)
		{
			node_type* node = _node;

			while (nth-- > 0 && node)
				node = node->next;

			return Iterator(node);
		}


		kint Count() const
		{
			node_type* node = _node;
			kint n = 0;

			while (node)
			{
				n++;
				node = node->next;
			}

			return n;
		}

		kint Contains(const value_type& item) const
		{
			node_type* node = _node;
			ksize_t n = 0;

			while (node)
			{
				if (node->item == item)
					return n;

				node = node->next;
				n++;
			}

			return -1;
		}

		Iterator Find(const value_type& item) const
		{
			node_type* node = _node;

			while (node)
			{
				if (node->item == item)
					return Iterator(node);

				node = node->next;
			}

			return Iterator();
		}

		template <typename PRED>
		Iterator Predict(PRED f, const value_type& item) const
		{
			node_type* node = _node;

			while (node)
			{
				if (f(item, node->item))
					return Iterator(node);

				node = node->next;
			}

			return Iterator();
		}

		node_type* LastNode()
		{
			node_type* node = _node;

			if (node)
			{
				while (node->next)
					node = node->next;
			}

			return node;
		}

		template <typename FN>
		void ForEach(FN f, kpointer data)
		{
			for (node_type* node = _node; node; node = node->next)
				f(data, node->item);
		}

		template <typename FN>
		void LoopEach(FN f)
		{
			for (node_type* node = _node; node; node = node->next)
				f(node->item);
		}

		Iterator Begin()
		{
			return Iterator(_node);
		}

		Iterator End()
		{
			return Iterator();
		}

		Iterator Last()
		{
			return Iterator(LastNode());
		}

		ConstIterator ConstBegin() const
		{
			return ConstIterator(_node);
		}

		ConstIterator ConstEnd() const
		{
			return ConstIterator();
		}

		ConstIterator ConstLast() const
		{
			return ConstIterator(LastNode());
		}

		Iterator begin()
		{
			return Iterator(_node);
		}

		Iterator end()
		{
			return Iterator();
		}

		Iterator last()
		{
			return Iterator(LastNode());
		}

		ConstIterator cbegin() const
		{
			return ConstIterator(_node);
		}

		ConstIterator cend() const
		{
			return ConstIterator();
		}

		ConstIterator clast() const
		{
			return ConstIterator(LastNode());
		}
	};

	// hash
	template <typename KEY, typename MAP, typename HASH = tpl::Hash<KEY>, typename EQ = tpl::EqTo<KEY> >
	class HashTable : public MemBase
	{
		KCH_NOEC(HashTable);

	public:
		typedef HashTable<KEY, MAP, HASH, EQ> this_type;
		typedef KEY key_type;
		typedef MAP map_type;
		typedef HASH hash_type;
		typedef EQ eq_type;
		typedef _iter::HashNode<KEY, MAP> node_type;
		typedef _iter::HashConstIterator<KEY, MAP> ConstIterator;
		typedef _iter::HashIterator<KEY, MAP> Iterator;
		typedef typename node_type::value_type value_type;

		ksize_t _revision;
		ksize_t _bucket;
		ksize_t _count;
		node_type** _nodes;
		node_type* _frst;
		node_type* _last;

		HashTable()
			: _revision(0), _bucket(K_MIN_HASH), _count(0)
			, _nodes(k_new_zero(K_MIN_HASH, node_type*))
			, _frst(NULL), _last(NULL)
		{
		}

		~HashTable()
		{
			node_type* node;
			node_type* prev;

			for (node = _last; node; node = prev)
			{
				prev = node->prev;
				delete node;
			}

			k_delete(_nodes);
		}

		kint Count() const
		{
			return (kint)_count;
		}

		kint Bucket() const
		{
			return (kint)_bucket;
		}

		kint Revision() const
		{
			return (kint)_revision;
		}

		bool IsEmpty() const
		{
			return _count == 0;
		}

		bool IsHave() const
		{
			return _count != 0;
		}

		map_type& operator[](const key_type& key)
		{
			ksize_t hash;
			node_type** pnode = _InternalLookUpHash(key, hash);

			if (!*pnode)
			{
				_InternalAdd(pnode, hash, key);
				_InternalTestSize();
			}

			return (*pnode)->value.map;
		}

		Iterator Get(const key_type& key) const
		{
			node_type** pnode = _InternalLookUp(key);
			return Iterator(*pnode);
		}

		void Set(const value_type& value)
		{
			ksize_t hash;
			node_type** pnode = _InternalLookUpHash(value.key, hash);

			if (*pnode)
			{
				node_type* node = *pnode;
				MemTrait::Reconstruct(&node->value, value);
			}
			else
			{
				_InternalAdd(pnode, hash, value);
				_InternalTestSize();
			}
		}

		void Set(const key_type& key, const map_type& map)
		{
			ksize_t hash;
			node_type** pnode = _InternalLookUpHash(key, hash);

			if (*pnode)
			{
				node_type* node = *pnode;
				MemTrait::Reconstruct(&node->value.first, key);
				MemTrait::Reconstruct(&node->value.second, map);
			}
			else
			{
				_InternalAdd(pnode, hash, key, map);
				_InternalTestSize();
			}
		}

		void Clear()
		{
			_InternalEraseAll();
			_InternalTestSize();
		}

		bool Remove(const key_type& key)
		{
			node_type** pnode = _InternalLookUp(key);

			if (!*pnode)
				return false;
			else
			{
				_InternalEraseNode(&pnode);
				_InternalTestSize();
				return true;
			}
		}

		Iterator Remove(Iterator it)
		{
			node_type* node = it.node;

			if (node)
			{
				++it;
				_InternalErase(&node);
				_InternalTestSize();
			}

			return it;
		}

		void RemoveFirst()
		{
			_InternalErase(&_frst);
			_InternalTestSize();
		}

		void RemoveLast()
		{
			_InternalErase(&_last);
			_InternalTestSize();
		}

		Iterator First()
		{
			return Iterator(_last);
		}

		Iterator Last()
		{
			return Iterator(_frst);
		}

		Iterator Begin()
		{
			return Iterator(_last);
		}

		Iterator End()
		{
			return Iterator(NULL);
		}

		Iterator Null()
		{
			return Iterator(NULL);
		}

		Iterator Nil()
		{
			return Iterator(NULL);
		}

		ConstIterator ConstFirst() const
		{
			return ConstIterator(_last);
		}

		ConstIterator ConstLast() const
		{
			return ConstIterator(_frst);
		}

		ConstIterator ConstBegin() const
		{
			return ConstIterator(_last);
		}

		ConstIterator ConstEnd() const
		{
			return ConstIterator(NULL);
		}

		ConstIterator ConstNull() const
		{
			return ConstIterator(NULL);
		}

		ConstIterator ConstNil() const
		{
			return ConstIterator(NULL);
		}

		Iterator first()
		{
			return Iterator(_last);
		}

		Iterator last()
		{
			return Iterator(_frst);
		}

		Iterator begin()
		{
			return Iterator(_last);
		}

		Iterator end()
		{
			return Iterator(NULL);
		}

		Iterator null()
		{
			return Iterator(NULL);
		}

		Iterator nil()
		{
			return Iterator(NULL);
		}

		ConstIterator cfirst() const
		{
			return ConstIterator(_last);
		}

		ConstIterator clast() const
		{
			return ConstIterator(_frst);
		}

		ConstIterator cbegin() const
		{
			return ConstIterator(_last);
		}

		ConstIterator cend() const
		{
			return ConstIterator(NULL);
		}

		ConstIterator cnull() const
		{
			return ConstIterator(NULL);
		}

		ConstIterator cnil() const
		{
			return ConstIterator(NULL);
		}

	protected:
		node_type** _InternalLookUp(const key_type& key) const
		{
			hash_type dohash;
			eq_type doeq;
			ksize_t hash = dohash(key);
			node_type** pnode = &_nodes[hash % _bucket];
			node_type* node;

			while ((node = *pnode) != NULL)
			{
				if (node->hash == hash && doeq(node->value.first, key))
					break;

				pnode = &node->sib;
			}

			return pnode;
		}

		node_type** _InternalLookUpHash(const key_type& key, ksize_t& hash) const
		{
			hash_type dohash;
			eq_type doeq;
			hash = dohash(key);
			node_type** pnode = &_nodes[hash % _bucket];
			node_type* node;

			while ((node = *pnode) != NULL)
			{
				if (node->hash == hash && doeq(node->value.first, key))
					break;

				pnode = &node->sib;
			}

			return pnode;
		}

		void _InternalAdd(node_type** pnode, node_type* node)
		{
			if (_frst)
				_frst->prev = node;
			else
				_last = node;

			node->next = _frst;
			node->prev = NULL;
			_frst = node;

			*pnode = node;
			_revision++;
			_count++;
		}

		void _InternalAdd(node_type** pnode, ksize_t hash, const key_type& key, const map_type& map)
		{
			node_type* node = new node_type(hash, key, map);
			_InternalAdd(pnode, node);
		}

		void _InternalAdd(node_type** pnode, ksize_t hash, const key_type& key)
		{
			node_type* node = new node_type(hash, key);
			_InternalAdd(pnode, node);
		}

		void _InternalAdd(node_type** pnode, ksize_t hash, const value_type& value)
		{
			node_type* node = new node_type(hash, value);
			_InternalAdd(pnode, node);
		}

		void _InternalEraseNode(node_type** * ppnode)
		{
			node_type** pnode = *ppnode;
			node_type* node = *pnode;

			*pnode = node->sib;

			if (node->next)
				node->next->prev = node->prev;
			else
			{
				k_assert_eq(_last, node);
				_last = node->prev;
			}

			if (node->prev)
				node->prev->next = node->next;
			else
			{
				k_assert_eq(_frst, node);
				_frst = node->next;
			}

			delete node;

			_count--;
			_revision++;
		}

		void _InternalErase(node_type** pnode)
		{
			_InternalEraseNode(&pnode);
		}

		void _InternalEraseAll()
		{
			node_type* node;
			node_type* next;

			for (node = _frst; node; node = next)
			{
				next = node->next;
				delete node;
			}

			memset(_nodes, 0, _bucket * sizeof(node_type*));
			_last = _frst = NULL;
			_count = 0;
		}

		void _InternalTestSize()
		{
			ksize_t cnt = _count;
			ksize_t bkt = _bucket;

			if ((bkt >= 3 * cnt && bkt > K_MIN_HASH) ||
				(3 * bkt <= cnt && bkt < K_MAX_HASH))
				_InternalResize();
		}

		void _InternalResize()
		{
			ksize_t newbucket = k_primeclose(_count);	// K_MIN_HASH ~ K_MAX_HASH
			node_type** newnodes = k_new_zero(newbucket, node_type*);

			for (ksize_t i = 0; i < _bucket; i++)
			{
				node_type* node;
				node_type* next;
				ksize_t mask;

				for (node = _nodes[i]; node; node = next)
				{
					next = node->sib;
					mask = node->hash % newbucket;
					node->sib = newnodes[mask];
					newnodes[mask] = node;
				}
			}

			k_delete(_nodes);

			_nodes = newnodes;
			_bucket = newbucket;
		}
	};

	// mukum
	template <typename KEY, typename MAP, typename HASH = tpl::Hash<KEY>, typename EQ = tpl::EqTo<KEY> >
	struct Mukum : public MemBase
	{
	public:
		typedef Mukum<KEY, MAP, HASH, EQ> this_type;
		typedef KEY key_type;
		typedef MAP map_type;
		typedef HASH hash_type;
		typedef EQ eq_type;
		typedef _iter::MukumNode<KEY, MAP> node_type;
		typedef _iter::MukumConstIterator<KEY, MAP> ConstIterator;
		typedef _iter::MukumIterator<KEY, MAP> Iterator;
		typedef typename node_type::value_type value_type;

		ksize_t _revision;
		ksize_t _bucket;
		ksize_t _count;
		node_type** _nodes;

		Mukum()
			: _revision(0), _bucket(K_MIN_HASH), _count(0)
			, _nodes(k_new_zero(K_MIN_HASH, node_type*))
		{
		}

		~Mukum()
		{
			for (ksize_t i = 0; i < _bucket; i++)
			{
				node_type* node;
				node_type* next;

				for (node = _nodes[i]; node; node = next)
				{
					next = node->sib;
					delete node;
				}
			}

			k_delete(_nodes);
		}

		kint Count() const
		{
			return (kint)_count;
		}

		kint Bucket() const
		{
			return (kint)_bucket;
		}

		kint Revision() const
		{
			return (kint)_revision;
		}

		bool IsEmpty() const
		{
			return _count == 0;
		}

		bool IsHave() const
		{
			return _count != 0;
		}

		map_type& operator[](const key_type& key)
		{
			ksize_t hash;
			node_type** pnode = _InternalLookUpHash(key, hash);

			if (!*pnode)
			{
				_InternalAdd(pnode, hash, key);
				_InternalTestSize();
			}

			return (*pnode)->value.map;
		}

		Iterator Get(const key_type& key) const
		{
			node_type** pnode = _InternalLookUp(key);
			return Iterator(*pnode);
		}

		void Set(const value_type& value)
		{
			ksize_t hash;
			node_type** pnode = _InternalLookUpHash(value.key, hash);

			if (*pnode)
			{
				node_type* node = *pnode;
				MemTrait::Reconstruct(&node->value, value);
			}
			else
			{
				_InternalAdd(pnode, hash, value);
				_InternalTestSize();
			}
		}

		void Set(const key_type& key, const map_type& map)
		{
			ksize_t hash;
			node_type** pnode = _InternalLookUpHash(key, hash);

			if (*pnode)
			{
				node_type* node = *pnode;
				MemTrait::Reconstruct(&node->value.first, key);
				MemTrait::Reconstruct(&node->value.second, map);
			}
			else
			{
				_InternalAdd(pnode, hash, key, map);
				_InternalTestSize();
			}
		}

		bool Try(const value_type& value)
		{
			ksize_t hash;
			node_type** pnode = _InternalLookUpHash(value.key, hash);

			if (*pnode)
				return false;
			else
			{
				_InternalAdd(pnode, hash, value);
				_InternalTestSize();
				return true;
			}
		}

		bool Try(const key_type& key, const map_type& map)
		{
			ksize_t hash;
			node_type** pnode = _InternalLookUpHash(key, hash);

			if (*pnode)
				return false;
			else
			{
				_InternalAdd(pnode, hash, key, map);
				_InternalTestSize();
				return true;
			}
		}

		void Clear()
		{
			_InternalEraseAll();
			_InternalTestSize();
		}

		bool Remove(const key_type& key)
		{
			node_type** pnode = _InternalLookUp(key);

			if (!*pnode)
				return false;
			else
			{
				_InternalEraseNode(&pnode);
				_InternalTestSize();
				return true;
			}
		}

		void Remove(Iterator it)
		{
			node_type* node = it.node;

			if (node)
			{
				_InternalErase(&node);
				_InternalTestSize();
			}
		}

		Iterator Null()
		{
			return Iterator(NULL);
		}

		Iterator Nil()
		{
			return Iterator(NULL);
		}

		ConstIterator ConstNull()
		{
			return ConstIterator(NULL);
		}

		ConstIterator ConstNil()
		{
			return ConstIterator(NULL);
		}

		Iterator null()
		{
			return Iterator(NULL);
		}

		Iterator nil()
		{
			return Iterator(NULL);
		}

		ConstIterator cnull()
		{
			return ConstIterator(NULL);
		}

		ConstIterator cnil()
		{
			return ConstIterator(NULL);
		}

		template <typename F>
		void ForEach(F fn2, kpointer data) const
		{
			for (ksize_t i = 0; i < _bucket; i++)
			{
				for (node_type* node = _nodes[i]; node; node = node->sib)
					fn1(data, node->value);
			}
		}

		template <typename F>
		void LoopEach(F fn2) const
		{
			for (ksize_t i = 0; i < _bucket; i++)
			{
				for (node_type* node = _nodes[i]; node; node = node->sib)
					fn2(node->value.key, node->value.map);
			}
		}

		template <typename F>
		void LoopEachKey(F fn1) const
		{
			for (ksize_t i = 0; i < _bucket; i++)
			{
				for (node_type* node = _nodes[i]; node; node = node->sib)
					fn1(node->value.key);
			}
		}

		template <typename F>
		void LoopEachValue(F fn) const
		{
			for (ksize_t i = 0; i < _bucket; i++)
			{
				for (node_type* node = _nodes[i]; node; node = node->sib)
					fn(node->value.map);
			}
		}

	protected:
		node_type** _InternalLookUp(const key_type& key) const
		{
			hash_type dohash;
			eq_type doeq;
			ksize_t hash = dohash(key);
			node_type** pnode = &_nodes[hash % _bucket];
			node_type* node;

			while ((node = *pnode) != NULL)
			{
				if (node->hash == hash && doeq(node->value.first, key))
					break;

				pnode = &node->sib;
			}

			return pnode;
		}

		node_type** _InternalLookUpHash(const key_type& key, ksize_t& hash) const
		{
			hash_type dohash;
			eq_type doeq;
			hash = dohash(key);
			node_type** pnode = &_nodes[hash % _bucket];
			node_type* node;

			while ((node = *pnode) != NULL)
			{
				if (node->hash == hash && doeq(node->value.first, key))
					break;

				pnode = &node->sib;
			}

			return pnode;
		}

		void _InternalAdd(node_type** pnode, node_type* node)
		{
			*pnode = node;
			_revision++;
			_count++;
		}

		void _InternalAdd(node_type** pnode, ksize_t hash, const key_type& key, const map_type& map)
		{
			node_type* node = new node_type(hash, key, map);
			_InternalAdd(pnode, node);
		}

		void _InternalAdd(node_type** pnode, ksize_t hash, const key_type& key)
		{
			node_type* node = new node_type(hash, key);
			_InternalAdd(pnode, node);
		}

		void _InternalAdd(node_type** pnode, ksize_t hash, const value_type& value)
		{
			node_type* node = new node_type(hash, value);
			_InternalAdd(pnode, node);
		}

		void _InternalEraseNode(node_type** * ppnode)
		{
			node_type** pnode = *ppnode;
			node_type* node = *pnode;

			*pnode = node->sib;

			delete node;

			_count--;
			_revision++;
		}

		void _InternalErase(node_type** pnode)
		{
			_InternalEraseNode(&pnode);
		}

		void _InternalEraseAll()
		{
			for (ksize_t i = 0; i < _bucket; i++)
			{
				node_type* node;
				node_type* next;

				for (node = _nodes[i]; node; node = next)
				{
					next = node->sib;
					delete node;
				}
			}

			memset(_nodes, 0, _bucket * sizeof(node_type*));
			_count = 0;
		}

		void _InternalTestSize()
		{
			ksize_t cnt = _count;
			ksize_t bkt = _bucket;

			if ((bkt >= 3 * cnt && bkt > K_MIN_HASH) ||
				(3 * bkt <= cnt && bkt < K_MAX_HASH))
				_InternalResize();
		}

		void _InternalResize()
		{
			ksize_t newbucket = k_primeclose(_count);	// K_MIN_HASH ~ K_MAX_HASH
			node_type** newnodes = k_new_zero(newbucket, node_type*);;

			for (ksize_t i = 0; i < _bucket; i++)
			{
				node_type* node;
				node_type* next;
				ksize_t mask;

				for (node = _nodes[i]; node; node = next)
				{
					next = node->sib;
					mask = node->hash % newbucket;
					node->sib = newnodes[mask];
					newnodes[mask] = node;
				}
			}

			k_delete(_nodes);

			_nodes = newnodes;
			_bucket = newbucket;
		}
	};
}






















//////////////////////////////////////////////////////////////////////////
// string 
namespace tpl
{
	namespace _traits
	{
		// TCHAR
		template <typename TCHAR>
		class CharTraits
		{
		public:
			static kint Length(const TCHAR* str)
			{
				return 0;
			}

			static ksize_t Hash(const TCHAR* str, kbool igcase)
			{
				return 0;
			}
			static kint Compare(const TCHAR* s1, const TCHAR* s2, kbool igcase)
			{
				return 0;
			}

			static kint CompareLength(const TCHAR* left, const TCHAR* right, ksize_t len, bool igcase)
			{
				return 0;
			}

			static kint FormatLen(const TCHAR* fmt, va_list va)
			{
				return 0;
			}

			static kint Format(TCHAR* out, kint capa, const TCHAR* fmt, va_list va)
			{
				return 0;
			}

			static TCHAR* Upper(TCHAR* str)
			{
				return (TCHAR*)NULL;
			}

			static TCHAR* Lower(TCHAR* str)
			{
				return (TCHAR*)NULL;
			}

			static TCHAR* Reverse(TCHAR* str)
			{
				return (TCHAR*)NULL;
			}

			static TCHAR* Trim(TCHAR* str)
			{
				return (TCHAR*)NULL;
			}

			static TCHAR* TrimLeft(TCHAR* str)
			{
				return (TCHAR*)NULL;
			}

			static TCHAR* TrimRight(TCHAR* str)
			{
				return (TCHAR*)NULL;
			}

			static TCHAR* BreakChr(const TCHAR* str, const TCHAR* chrs)
			{
				return (TCHAR*)NULL;
			}

			static TCHAR* RemoveChr(TCHAR* str, const TCHAR* chrs)
			{
				return (TCHAR*)NULL;
			}

			static TCHAR* Find(const TCHAR* str, const TCHAR* find)
			{
				return (TCHAR*)NULL;
			}

			static TCHAR* FindChar(const TCHAR* str, TCHAR ch)
			{
				return (TCHAR*)NULL;
			}

			static TCHAR* Mid(TCHAR* dest, const TCHAR* src, ksize_t pos, ksize_t len)
			{
				return (TCHAR*)NULL;
			}

			static ksize_t Fill(TCHAR* dest, ksize_t pos, ksize_t end, TCHAR ch)
			{
				return 0;
			}
		};

		// char
		template <>
		class CharTraits<char>
		{
		public:
			static kint Length(const char* str)
			{
				return !str ? 0 : (kint)k_strlen(str);
			}

			static ksize_t Hash(const char* str, kbool igcase)
			{
				return igcase ? k_strihash(str) : k_strhash(str);
			}

			static kint Compare(const char* left, const char* right, bool igcase)
			{
				return igcase ? k_stricmp(left, right) : k_strcmp(left, right);
			}

			static kint CompareLength(const char* left, const char* right, ksize_t len, bool igcase)
			{
				return igcase ? k_strnicmp(left, right, len) : k_strncmp(left, right, len);
			}

			static kint FormatLen(const char* fmt, va_list va)
			{
				return k_vsnprintf(NULL, 0, fmt, va);
			}

			static kint Format(char* out, kint capa, const char* fmt, va_list va)
			{
				return k_vsnprintf(out, capa, fmt, va);
			}

			static char* Upper(char* str)
			{
				return k_strupr(str);
			}

			static char* Lower(char* str)
			{
				return k_strlwr(str);
			}

			static char* Reverse(char* str)
			{
				return k_strrev(str);
			}

			static char* Trim(char* str)
			{
				return k_strtrim(str);
			}

			static char* TrimLeft(char* str)
			{
				return k_strltrim(str);
			}

			static char* TrimRight(char* str)
			{
				return k_strrtrim(str);
			}

			static char* BreakChr(const char* str, const char* chrs)
			{
				return k_strbrk(str, chrs);
			}

			static char* RemoveChr(char* str, const char* chrs)
			{
				return k_strrem(str, chrs);
			}

			static char* Find(const char* str, const char* find)
			{
				return k_strstr(str, find);
			}

			static char* FindChar(const char* str, char ch)
			{
				return k_strchr(str, ch);
			}

			static char* Mid(char* dest, const char* src, ksize_t pos, ksize_t len)
			{
				return k_strmid(dest, src, pos, len);
			}

			static ksize_t Fill(char* dest, ksize_t pos, ksize_t end, char ch)
			{
				return k_strfll(dest, pos, end, ch);
			}
		};

		// wchar
		template <>
		class CharTraits<kwchar>
		{
		public:
			static kint Length(const kwchar* wcs)
			{
				return !wcs ? 0 : (kint)k_wcslen(wcs);
			}

			static ksize_t Hash(const kwchar* wcs, kbool igcase)
			{
				return igcase ? k_wcsihash(wcs) : k_wcshash(wcs);
			}

			static kint Compare(const kwchar* left, const kwchar* right, bool igcase)
			{
				return igcase ? k_wcsicmp(left, right) : k_wcscmp(left, right);
			}

			static kint CompareLength(const kwchar* left, const kwchar* right, ksize_t len, bool igcase)
			{
				return igcase ? k_wcsnicmp(left, right, len) : k_wcsncmp(left, right, len);
			}

			static kint FormatLen(const kwchar* fmt, va_list va)
			{
				return k_vsnwprintf(NULL, 0, fmt, va);
			}

			static kint Format(kwchar* out, kint capa, const kwchar* fmt, va_list va)
			{
				return k_vsnwprintf(out, capa, fmt, va);
			}

			static kwchar* Upper(kwchar* wcs)
			{
				return k_wcsupr(wcs);
			}

			static kwchar* Lower(kwchar* wcs)
			{
				return k_wcslwr(wcs);
			}

			static kwchar* Reverse(kwchar* wcs)
			{
				return k_wcsrev(wcs);
			}

			static kwchar* Trim(kwchar* wcs)
			{
				return k_wcstrim(wcs);
			}

			static kwchar* TrimLeft(kwchar* wcs)
			{
				return k_wcsltrim(wcs);
			}

			static kwchar* TrimRight(kwchar* wcs)
			{
				return k_wcsrtrim(wcs);
			}

			static kwchar* BreakChr(const kwchar* wcs, const kwchar* chrs)
			{
				return k_wcsbrk(wcs, chrs);
			}

			static kwchar* RemoveChr(kwchar* wcs, const kwchar* chrs)
			{
				return k_wcsrem(wcs, chrs);
			}

			static kwchar* Find(const kwchar* wcs, const kwchar* find)
			{
				return k_wcsstr(wcs, find);
			}

			static kwchar* FindChar(const kwchar* str, kwchar ch)
			{
				return k_wcschr(str, ch);
			}

			static kwchar* Mid(kwchar* dest, const kwchar* src, ksize_t pos, ksize_t len)
			{
				return k_wcsmid(dest, src, pos, len);
			}

			static ksize_t Fill(kwchar* dest, ksize_t pos, ksize_t end, kwchar ch)
			{
				return k_wcsfll(dest, pos, end, ch);
			}
		};
	}

	// blue string
	template <typename TCHAR, ksize_t SIZE>
	class BasicBls
	{
	public:
		typedef BasicBls<TCHAR, SIZE> this_type;
		typedef TCHAR value_type;
		typedef _traits::CharTraits<value_type> trait_type;
		typedef const value_type* ConstIterator;
		typedef value_type* Iterator;

		kint _len;
		value_type _data[SIZE];

		BasicBls()
			: _len(0)
		{
			_data[0] = (value_type)0;
		}

		BasicBls(const BasicBls& right)
		{
			if (right._len)
			{
				_len = right._len;
				memcpy(_data, right._data, _len * sizeof(value_type));
				_data[_len] = (value_type)0;
			}
			else
			{
				_len = 0;
				_data[0] = (value_type)0;
			}
		}

		BasicBls(const value_type* str, kint len = -1)
		{
			if (!str)
			{
				_len = 0;
				_data[0] = (value_type)0;
			}
			else
			{
				if (len < 0)
					_len = trait_type::Length(str);
				else
				{
					kint tmplen = trait_type::Length(str);
					_len = K_MIN(tmplen, len);
				}

				memcpy(_data, str, _len * sizeof(value_type));
				_data[_len] = (value_type)0;
			}
		}

		BasicBls(value_type ch)
		{
			_len = 1;
			_data[0] = ch;
			_data[1] = (value_type)0;
		}

		BasicBls& operator=(const BasicBls& right)
		{
			if (this != &right)
			{
				if (right._len)
				{
					_len = right._len;
					memcpy(_data, right._data, _len * sizeof(value_type));
					_data[_len] = (value_type)0;
				}
				else
				{
					_len = 0;
					_data[0] = (value_type)0;
				}
			}

			return *this;
		}

		BasicBls& operator=(const value_type* right)
		{
			if (!right)
			{
				_len = 0;
				_data[0] = (value_type)0;
			}
			else
			{
				_len = trait_type::Length(right);
				memcpy(_data, right, _len * sizeof(value_type));
				_data[_len] = (value_type)0;
			}

			return *this;
		}

		BasicBls& operator=(value_type right)
		{
			_len = 1;
			_data[0] = right;
			_data[1] = (value_type)0;
			return *this;
		}

		BasicBls& operator+=(const BasicBls& right)
		{
			memcpy(&_data[_len], right._data, right._len * sizeof(value_type));
			_len += right._len;
			_data[_len] = (value_type)0;
			return *this;
		}

		BasicBls& operator+=(const value_type* right)
		{
			kint tlen = trait_type::Length(right);
			memcpy(&_data[_len], right, tlen * sizeof(value_type));
			_len += tlen;
			_data[_len] = (value_type)0;
			return *this;
		}

		BasicBls& operator+=(value_type ch)
		{
			_data[_len] = ch;
			_data[++_len] = (value_type)0;
			return *this;
		}

		TCHAR operator[](kint index) const
		{
			return _data[index];
		}

		TCHAR& operator[](kint index)
		{
			return _data[index];
		}

		const TCHAR* Data() const
		{
			return _data;
		}

		TCHAR* Data()
		{
			return _data;
		}

		bool IsEmpty() const
		{
			return _len == 0;
		}

		bool IsHave() const
		{
			return _len != 0;
		}

		kint Length() const
		{
			return _len;
		}

		ksize_t Maximum() const
		{
			return SIZE;
		}

		ksize_t Hash(kbool igcase = false) const
		{
			return trait_type::Hash(_data, igcase);
		}

		void Intern()
		{
			_len = trait_type::Length(_data);
		}

		void Truncate(kint n)
		{
			_len = n;
			_data[n] = (value_type)0;
		}

		void Zero()
		{
			_len = 0;
			_data[0] = (value_type)0;
		}

		void Set(const BasicBls& right)
		{
			if (this != &right)
			{
				if (right._len)
				{
					_len = right._len;
					memcpy(_data, right._data, _len * sizeof(value_type));
					_data[_len] = (value_type)0;
				}
				else
				{
					_len = 0;
					_data[0] = (value_type)0;
				}
			}
		}

		void Set(const value_type* str, kint len = -1)
		{
			if (!str)
			{
				_len = 0;
				_data[0] = (value_type)0;
			}
			else if (_data != str)
			{
				if (len < 0)
					_len = trait_type::Length(str);
				else
				{
					kint tmplen = trait_type::Length(str);
					_len = K_MIN(tmplen, len);
				}

				memcpy(_data, str, _len * sizeof(value_type));
				_data[_len] = (value_type)0;
			}
		}

		void Set(value_type ch)
		{
			_len = 1;
			_data[0] = ch;
			_data[1] = (value_type)0;
		}

		void Format(const value_type* fmt, ...)
		{
			va_list va;
			va_start(va, fmt);
			_len = trait_type::Format(_data, SIZE - 1, fmt, va);
			va_end(va);
		}

		void FormatVa(const value_type* fmt, va_list va)
		{
			_len = trait_type::Format(_data, SIZE - 1, fmt, va);
		}

		void AppendFormat(const value_type* fmt, ...)
		{
			va_list va;
			va_start(va, fmt);
			_len += trait_type::Format(_data + _len, SIZE - _len - 1, fmt, va);
			va_end(va);
		}

		void AppendFormatVa(const value_type* fmt, va_list va)
		{
			_len += trait_type::Format(_data + _len, SIZE - _len - 1, fmt, va);
		}

		void Lower()
		{
			trait_type::Lower(_data);
		}

		void Upper()
		{
			trait_type::Upper(_data);
		}

		void TrimFill(ksize_t pos, ksize_t end, value_type ch)
		{
			ksize_t n = trait_type::Fill(_data, pos, end < SIZE ? end : SIZE - 1, ch);
			_len = n;
			_data[n] = (value_type)0;
		}

		void TrimFill(ksize_t count, value_type ch)
		{
			TrimFill(0, count, ch);
		}

		void Fill(ksize_t pos, ksize_t end, value_type ch)
		{
			kint n = (kint)trait_type::Fill(_data, pos, end < SIZE ? end : SIZE - 1, ch);
			if (n > _len)
			{
				_len = n;
				_data[n] = (value_type)0;
			}
		}

		void Fill(ksize_t count, value_type ch)
		{
			Fill(0, count, ch);
		}

		kint HasChars(const value_type* chars) const
		{
			TCHAR* s = trait_type::BreakChr(_data, chars);
			return s ? (kint)(s - _data) : -1;
		}

		kint Find(kint at, const BasicBls& bs) const
		{
			return Find(at, bs._data);
		}

		kint Find(kint at, const value_type* str) const
		{
			TCHAR* s = trait_type::Find(_data + at, str);
			return s ? (kint)(s - _data) : -1;
		}

		kint Find(kint at, value_type ch) const
		{
			TCHAR* s = trait_type::FindChar(_data + at, ch);
			return s ? (kint)(s - _data) : -1;
		}

		kint Find(const BasicBls& bs) const
		{
			return Find(0, bs._data);
		}

		kint Find(const value_type* str) const
		{
			return Find(0, str);
		}

		kint Find(value_type ch) const
		{
			return Find(0, ch);
		}

		bool Contains(const BasicBls& bls) const
		{
			return Find(bls) >= 0;
		}

		bool Contains(const value_type* str) const
		{
			return Find(str) >= 0;
		}

		bool Contains(value_type ch) const
		{
			return Find(ch) >= 0;
		}

		kint CompareTo(const value_type* str, bool igcase = false) const
		{
			return trait_type::Compare(_data, str, igcase);
		}

		kint CompareTo(const BasicBls& bs, bool igcase = false) const
		{
			return trait_type::Compare(_data, bs._data, igcase);
		}

		kint CompareLengthTo(const value_type* str, ksize_t len, bool igcase = false) const
		{
			return trait_type::CompareLength(_data, str, len, igcase);
		}

		kint CompareLengthTo(const BasicBls& bs, ksize_t len, bool igcase = false) const
		{
			return trait_type::CompareLength(_data, bs._data, len, igcase);
		}

		BasicBls SubString(kint pos = 0, kint len = -1) const
		{
			if (pos < 0)
				pos = 0;

			if (len < 0) len = _len - pos;

			if ((pos + len) > _len)
				len = _len - pos;

			if (pos > _len)
				len = 0;

			BasicBls bs;
			trait_type::Mid(bs._data, _data, pos, len);
			bs._len = trait_type::Length(bs._data);
			return bs;
		}

		void Trim()
		{
			_len = trait_type::Length(trait_type::Trim(_data));
		}

		void TrimLeft()
		{
			_len = trait_type::Length(trait_type::TrimLeft(_data));
		}

		void TrimRight()
		{
			_len = trait_type::Length(trait_type::TrimRight(_data));
		}

		void RemoveChars(const value_type* rmlist)
		{
			_len = trait_type::Length(trait_type::RemoveChr(_data, rmlist));
		}

		bool RemoveAt(kint nth, kint cnt = 1)
		{
			if (!_len || nth < 0 || nth >= _len || cnt <= 0)
				return false;

			if ((nth + cnt) > _len)
				cnt = _len - nth;

			memmove(_data + nth, _data + nth + cnt, (_len - nth - cnt + 1)*sizeof(value_type));
			_len--;

			return true;
		}

		bool Insert(kint nth, const value_type* str, kint cnt = -1)
		{
			if (nth < 0)
				return false;

			if (nth > _len)
				return false;

			if (cnt < 0)
				cnt = trait_type::Length(str);

			if ((_len + cnt) >= SIZE)
				return false;

			memmove(_data + nth + cnt, _data + nth, (_len - nth + 1)*sizeof(value_type));
			memcpy(_data + nth, str, cnt * sizeof(value_type));
			_len += cnt;

			return true;
		}

		bool Insert(kint nth, value_type ch)
		{
			if (nth < 0 || nth > _len)
				return false;

			if ((_len + 1) >= SIZE)
				return false;

			TCHAR* s = _data + _len;
			TCHAR* d = _data + _len + 1;
			TCHAR* p = _data + nth;

			while (d > p)
				*d-- = *s--;

			_data[nth] = ch;
			_len++;

			return true;
		}

		Iterator Begin() const
		{
			return Iterator(&_data[0]);
		}

		Iterator End() const
		{
			return Iterator(&_data[_len]);
		}

		Iterator First() const
		{
			return Iterator(&_data[0]);
		}

		Iterator Last() const
		{
			return Iterator(&_data[_len - 1]);
		}

		ConstIterator ConstBegin() const
		{
			return ConstIterator(&_data[0]);
		}


		ConstIterator ConstEnd() const
		{
			return ConstIterator(&_data[_len]);
		}

		ConstIterator ConstFirst() const
		{
			return ConstIterator(&_data[0]);
		}

		ConstIterator ConstLast() const
		{
			return ConstIterator(&_data[_len - 1]);
		}

		Iterator begin() const
		{
			return Iterator(&_data[0]);
		}

		Iterator end() const
		{
			return Iterator(&_data[_len]);
		}

		Iterator first() const
		{
			return Iterator(&_data[0]);
		}

		Iterator last() const
		{
			return Iterator(&_data[_len - 1]);
		}

		ConstIterator cbegin() const
		{
			return ConstIterator(&_data[0]);
		}

		ConstIterator cend() const
		{
			return ConstIterator(&_data[_len]);
		}

		ConstIterator cfirst() const
		{
			return ConstIterator(&_data[0]);
		}

		ConstIterator clast() const
		{
			return ConstIterator(&_data[_len - 1]);
		}
	};

	template <typename TCHAR, ksize_t SIZE>
	inline bool operator==(const BasicBls<TCHAR, SIZE>& left, const BasicBls<TCHAR, SIZE>& right)
	{
		return BasicBls<TCHAR, SIZE>::trait_type::Compare(left._data, right._data, false) == 0;
	}

	template <typename TCHAR, ksize_t SIZE>
	inline bool operator!=(const BasicBls<TCHAR, SIZE>& left, const BasicBls<TCHAR, SIZE>& right)
	{
		return BasicBls<TCHAR, SIZE>::trait_type::Compare(left._data, right._data, false) != 0;
	}

	template <typename TCHAR, ksize_t SIZE>
	inline bool operator==(const BasicBls<TCHAR, SIZE>& left, const TCHAR* right)
	{
		return BasicBls<TCHAR, SIZE>::trait_type::Compare(left._data, right, false) == 0;
	}

	template <typename TCHAR, ksize_t SIZE>
	inline bool operator!=(const BasicBls<TCHAR, SIZE>& left, const TCHAR* right)
	{
		return BasicBls<TCHAR, SIZE>::trait_type::Compare(left._data, right, false) != 0;
	}

	template <typename TCHAR, ksize_t SIZE>
	inline bool operator==(const TCHAR* left, const BasicBls<TCHAR, SIZE>& right)
	{
		return BasicBls<TCHAR, SIZE>::trait_type::Compare(left, right._data, false) == 0;
	}

	template <typename TCHAR, ksize_t SIZE>
	inline bool operator!=(const TCHAR* left, const BasicBls<TCHAR, SIZE>& right)
	{
		return BasicBls<TCHAR, SIZE>::trait_type::Compare(left, right._data, false) != 0;
	}

	template <typename TCHAR, ksize_t SIZE>
	inline BasicBls<TCHAR, SIZE> operator+(const BasicBls<TCHAR, SIZE>& left, const BasicBls<TCHAR, SIZE>& right)
	{
		BasicBls<TCHAR, SIZE> bs(left);
		bs += right;
		return bs;
	}

	template <typename TCHAR, ksize_t SIZE>
	inline BasicBls<TCHAR, SIZE> operator+(const BasicBls<TCHAR, SIZE>& left, const TCHAR* right)
	{
		BasicBls<TCHAR, SIZE> bs(left);
		bs += right;
		return bs;
	}

	template <typename TCHAR, ksize_t SIZE>
	inline BasicBls<TCHAR, SIZE> operator+(const BasicBls<TCHAR, SIZE>& left, TCHAR right)
	{
		BasicBls<TCHAR, SIZE> bs(left);
		bs += right;
		return bs;
	}

	template <typename TCHAR, ksize_t SIZE>
	inline BasicBls<TCHAR, SIZE> operator+(const TCHAR* left, const BasicBls<TCHAR, SIZE>& right)
	{
		BasicBls<TCHAR, SIZE> bs(left);
		bs += right;
		return bs;
	}

	template <typename TCHAR, ksize_t SIZE>
	inline BasicBls<TCHAR, SIZE> operator+(TCHAR left, const BasicBls<TCHAR, SIZE>& right)
	{
		BasicBls<TCHAR, SIZE> bs(left);
		bs += right;
		return bs;
	}

	// string
	template <typename TCHAR>
	struct BasicString : public MemBase
	{
		typedef BasicString<TCHAR> this_type;
		typedef TCHAR value_type;
		typedef _traits::CharTraits<value_type> trait_type;
		typedef const value_type* ConstIterator;
		typedef value_type* Iterator;

		value_type* _data;

		BasicString()
			: _data(_InternalStaticEmptyString()._data)
		{
		}

		BasicString(const BasicString& right)
		{
			if (right._InternalData()->ref >= 0)
			{
				_data = right._data;
				k_atominc(&_InternalData()->ref);
			}
			else
			{
				_data = _InternalStaticEmptyString()._data;
				*this = right._data;
			}
		}

		BasicString(const value_type* right)
		{
			_data = _InternalStaticEmptyString()._data;

			if (right)
			{
				kint len = trait_type::Length(right);

				if (len > 0)
				{
					_InternalAlloc(len);
					memcpy(_data, right, len * sizeof(value_type));
				}
			}
		}

		BasicString(const value_type* str, kint len)
		{
			_data = _InternalStaticEmptyString()._data;

			if (len > 0)
			{
				_InternalAlloc(len);
				memcpy(_data, str, len * sizeof(value_type));
			}
		}

		~BasicString()
		{
			if (_InternalData() != _k_str_nil_data)
			{
				if (k_atomdec(&_InternalData()->ref) <= 0)
					k_delete((kbyte*)_InternalData());
			}
		}

		BasicString& operator=(const BasicString& str)
		{
			if (_data != str._data)
			{
				if ((_InternalData()->ref < 0 && _InternalData() != _k_str_nil_data) || str._InternalData()->ref < 0)
					_InternalAssign(str._data, str.Length());
				else
				{
					_InternalRelease();
					_data = str._data;
					k_atominc(&_InternalData()->ref);
				}
			}

			return *this;
		}

		BasicString& operator=(const value_type* str)
		{
			_InternalAssign(str, trait_type::Length(str));
			return *this;
		}

		BasicString& operator=(value_type ch)
		{
			_InternalAssign(&ch, 1);
			return *this;
		}

		BasicString& operator+=(const BasicString& str)
		{
			_InternalAppend(str._data, str.Length());
			return *this;
		}

		BasicString& operator+=(const value_type* str)
		{
			_InternalAppend(str, trait_type::Length(str));
			return *this;
		}

		BasicString& operator+=(value_type ch)
		{
			_InternalAppend(&ch, 1);
			return *this;
		}

		//
		const value_type operator[](kint index) const
		{
			return _data[index];
		}

		value_type& operator[](kint index)
		{
			_InternalCommitCopy();
			return _data[index];
		}

		operator const value_type* () const
		{
			return _data;
		}

		operator value_type* ()
		{
			_InternalCommitCopy();
			return _data;
		}

		const value_type* ConstData() const
		{
			return _data;
		}

		const value_type* Data() const
		{
			return _data;
		}

		value_type* Data()
		{
			_InternalCommitCopy();
			return _data;
		}

		bool IsEmpty() const
		{
			return _InternalData()->len == 0;
		}

		bool IsHave() const
		{
			return _InternalData()->len != 0;
		}

		kint Length() const
		{
			return _InternalData()->len;
		}

		ksize_t Hash(kbool igcase = false) const
		{
			return trait_type::Hash(_data, igcase);
		}

		kint Compare(const value_type* str, bool igcase = false) const
		{
			return trait_type::Compare(_data, str, igcase);
		}

		void Zero()
		{
			if (_InternalData()->len != 0)
			{
				if (_InternalData()->ref >= 0)
					_InternalRelease();
				else
				{
					_InternalCommitAlloc(0);
					_InternalData()->len = 0;
					_data[0] = (TCHAR)'\0';
				}
			}
		}

		void Format(const value_type* fmt, ...)
		{
			va_list va;
			va_start(va, fmt);
			FormatVa(fmt, va);
			va_end(va);
		}

		void FormatVa(const value_type* fmt, va_list va)
		{
			kint len = trait_type::FormatLen(fmt, va);

			if (_InternalBuffer(len))
			{
				trait_type::Format(_data, _InternalData()->capa + 1, fmt, va);
				_InternalDelete();
			}
		}

		void Upper()
		{
			_InternalCommitCopy();
			trait_type::Upper(_data);
		}

		void Lower()
		{
			_InternalCommitCopy();
			trait_type::Lower(_data);
		}

		void Reverse()
		{
			_InternalCommitCopy();
			trait_type::Reverse(_data);
		}

		void Trim()
		{
			_InternalCommitCopy();
			_InternalData()->len = trait_type::Length(trait_type::Trim(_data));
		}

		void TrimLeft()
		{
			_InternalCommitCopy();
			_InternalData()->len = trait_type::Length(trait_type::TrimLeft(_data));
		}

		void TrimRight()
		{
			_InternalCommitCopy();
			_InternalData()->len = trait_type::Length(trait_type::TrimRight(_data));
		}

		kint HasChars(const value_type* chrs) const
		{
			char* s = trait_type::BreakChr(_data, chrs);
			return s ? (kint)(s - _data) : -1;
		}

		void RemoveChars(const value_type* chrs)
		{
			_InternalCommitCopy();
			_InternalData()->len = trait_type::Length(trait_type::RemoveChr(_data, chrs));
		}

		BasicString SubString(kint pos = 0, kint len = -1) const
		{
			if (pos < 0) pos = 0;

			if (len < 0) len = _InternalData()->len - pos;

			if ((pos + len) > _InternalData()->len)
				len = _InternalData()->len - pos;

			if (pos > _InternalData()->len)
				len = 0;

			BasicString s;
			_InternalCopy(s, len, pos, 0);
			return s;
		}

		BasicString Left(kint cnt) const
		{
			if (cnt < 0)
				cnt = 0;
			else if (cnt > _InternalData()->len)
				cnt = _InternalData()->len;

			BasicString s;
			_InternalCopy(s, cnt, 0, 0);
			return s;
		}

		BasicString Right(kint cnt) const
		{
			if (cnt < 0)
				cnt = 0;
			else if (cnt > _InternalData()->len)
				cnt = _InternalData()->len;

			BasicString s;
			_InternalCopy(s, cnt, _InternalData()->len - cnt, 0);
			return s;
		}

		bool Insert(kint nth, const value_type* str, kint cnt = -1)
		{
			if (nth < 0)
				return false;

			if (cnt < 0)
				cnt = trait_type::Length(str);

			kint nl = _InternalData()->len;
			_InternalCommitCopy();

			if (nth > nl)
				nth = nl;

			nl += cnt;

			kStrData* old = _InternalData();

			if (old->capa < nl)
			{
				const TCHAR* prev = _data;
				_InternalAlloc(nl);
				memcpy(_data, prev, (old->len + 1)*sizeof(value_type));
				_InternalStaticRelease(old);
			}

			memmove(_data + nth + cnt, _data + nth, (nl - nth - cnt + 1)*sizeof(value_type));
			memcpy(_data + nth, str, cnt * sizeof(value_type));
			_InternalData()->len = nl;

			return true;
		}

		bool Insert(kint nth, value_type ch)
		{
			_InternalCommitCopy();

			if (nth < 0)
				return false;

			kint nl = _InternalData()->len;

			if (nth > nl)
				nth = nl;

			nl++;

			kStrData* old = _InternalData();

			if (old->capa < nl)
			{
				const TCHAR* prev = _data;
				_InternalAlloc(nl);
				memcpy(_data, prev, (old->len + 1)*sizeof(value_type));
				_InternalStaticRelease(old);
			}

			memmove(_data + nth + 1, _data + nth, (nl - nth)*sizeof(value_type));
			_data[nth] = ch;
			_InternalData()->len = nl;

			return true;
		}

		bool RemoveAt(kint nth, kint cnt = 1)
		{
			kint l = _InternalData()->len;

			if (nth < 0 || (nth >= l && cnt <= 0))
				return false;

			if ((nth + cnt) > l)
				cnt = l - nth;

			_InternalCommitCopy();

			//kint t = l - (nth + cnt) + 1;
			memmove(_data + nth, _data + nth + cnt, (l - nth - cnt + 1)*sizeof(value_type));
			_InternalData()->len = l - cnt;

			return true;
		}

		kint Find(kint at, const BasicString& str) const
		{
			return Find(at, str._data);
		}

		kint Find(kint at, const value_type* str) const
		{
			TCHAR* s = trait_type::Find(_data + at, str);
			return s ? (kint)(s - _data) : -1;
		}

		kint Find(kint at, value_type ch) const
		{
			TCHAR* s = trait_type::FindChar(_data + at, ch);
			return s ? (kint)(s - _data) : -1;
		}

		kint Find(const BasicString& bs) const
		{
			return Find(0, bs._data);
		}

		kint Find(const value_type* str) const
		{
			return Find(0, str);
		}

		kint Find(value_type ch) const
		{
			return Find(0, ch);
		}

		const value_type* Lock()
		{
			const value_type* psz = _InternalBuffer(0);

			if (psz)
				_InternalData()->ref = -1;

			return psz;
		}

		void Unlock()
		{
			if (_InternalData() != _k_str_nil_data)
				_InternalData()->ref = 1;
		}

		Iterator Begin()
		{
			_InternalCommitCopy();
			return Iterator(&_data[0]);
		}

		Iterator End()
		{
			_InternalCommitCopy();
			return Iterator(&_data[_InternalData()->len]);
		}

		Iterator First()
		{
			_InternalCommitCopy();
			return Iterator(&_data[0]);
		}

		Iterator Last()
		{
			_InternalCommitCopy();
			return Iterator(&_data[_InternalData()->len - 1]);
		}

		ConstIterator ConstBegin() const
		{
			return ConstIterator(&_data[0]);
		}

		ConstIterator ConstEnd() const
		{
			return ConstIterator(&_data[_InternalData()->len]);
		}

		ConstIterator ConstFirst() const
		{
			return ConstIterator(&_data[0]);
		}

		ConstIterator ConstLast() const
		{
			return ConstIterator(&_data[_InternalData()->len - 1]);
		}

		Iterator begin()
		{
			_InternalCommitCopy();
			return Iterator(&_data[0]);
		}

		Iterator end()
		{
			_InternalCommitCopy();
			return Iterator(&_data[_InternalData()->len]);
		}

		Iterator first()
		{
			_InternalCommitCopy();
			return Iterator(&_data[0]);
		}

		Iterator last()
		{
			_InternalCommitCopy();
			return Iterator(&_data[_InternalData()->len - 1]);
		}

		ConstIterator cbegin() const
		{
			return ConstIterator(&_data[0]);
		}

		ConstIterator cend() const
		{
			return ConstIterator(&_data[_InternalData()->len]);
		}

		ConstIterator cfirst() const
		{
			return ConstIterator(&_data[0]);
		}

		ConstIterator clast() const
		{
			return ConstIterator(&_data[_InternalData()->len - 1]);
		}

	protected:
		static const BasicString& _InternalStaticEmptyString()
		{
			return *(BasicString*)&_k_str_nil_ptr;
		}

		kStrData* _InternalData() const
		{
			return ((kStrData*)_data) - 1;
		}

		bool _InternalAlloc(kint len)
		{
			if (len <= 0)
				_data = _InternalStaticEmptyString()._data;
			else
			{
				kStrData* data = (kStrData*)k_new(sizeof(kStrData)+(len + 1) * sizeof(value_type), kbyte);
				k_return_value_if_fail(data, false);

				data->ref = 1;
				data->len = len;
				data->capa = len;

				_data = (value_type*)(data + 1);
				_data[len] = (value_type)0;
			}

			return true;
		}

		void _InternalDelete(kint len = -1)
		{
			_InternalCommitCopy();

			if (len < 0)
				len = trait_type::Length(_data);

			_InternalData()->len = len;
			_data[len] = (value_type)0;
		}

		void _InternalRelease()
		{
			if (_InternalData() != _k_str_nil_data)
			{
				if (k_atomdec(&_InternalData()->ref) <= 0)
					k_delete((kbyte*)_InternalData());

				_data = _InternalStaticEmptyString()._data;
			}
		}

		static void _InternalStaticRelease(kStrData* data)
		{
			if (data != _k_str_nil_data)
			{
				if (k_atomdec(&data->ref) <= 0)
					k_delete((kbyte*)data);
			}
		}

		void _InternalCommitCopy()
		{
			kStrData* data = _InternalData();

			if (data->ref > 1)
			{
				_InternalRelease();

				if (_InternalAlloc(data->len))
					memcpy(_data, (const value_type*)(data + 1), (data->len + 1) * sizeof(value_type));
			}
		}

		void _InternalCommitAlloc(kint len)
		{
			if (_InternalData()->ref > 1 || len > _InternalData()->capa)
			{
				_InternalRelease();
				_InternalAlloc(len);
			}
		}

		const char* _InternalBuffer(kint minlen)
		{
			kStrData* old = _InternalData();

			if (old->ref > 1 || minlen > old->capa)
			{
				kint ol = old->len;

				if (minlen < ol)
					minlen = ol;

				_InternalAlloc(minlen);

				memcpy(_data, old + 1, (ol + 1) * sizeof(value_type));
				_InternalData()->len = ol;
				_InternalStaticRelease(old);
			}

			return _data;
		}

		bool _InternalCopy(BasicString& s, kint len, kint idx, kint ext) const
		{
			int nl = len + ext;

			if (nl == 0)
				return true;
			else if (nl > len)
			{
				if (s._InternalAlloc(nl))
					memcpy(s._data, _data + idx, len * sizeof(value_type));
			}

			return true;
		}

		void _InternalAssign(const value_type* str, kint len)
		{
			_InternalCommitAlloc(len);
			memcpy(_data, str, len * sizeof(value_type));
			_InternalData()->len = len;
			_data[len] = (value_type)0;
		}

		bool _InternalConcat(const value_type* s1, kint l1, const value_type* s2, kint l2)
		{
			kint nl = l1 + l2;
#if 0
			if (nl < l1 || nl < l2)
				return false;
			else
#endif
			if (nl > 0)
			{
				_InternalAlloc(nl);
				memcpy(_data, s1, l1 * sizeof(value_type));
				memcpy(_data + l1, s2, l2 * sizeof(value_type));
			}

			return true;
		}

		void _InternalAppend(const value_type* str, kint  len)
		{
			k_return_if_fail(len > 0);

			kStrData* old = _InternalData();

			if (old->ref > 1 || old->len + len > old->capa)
			{
				if (_InternalConcat(_data, old->len, str, len))
					_InternalStaticRelease(old);
			}
			else
			{
				memcpy(_data + old->len, str, len * sizeof(value_type));
				old->len += len;
				_data[old->len] = (value_type)0;
			}
		}
	};

	template <typename TCHAR>
	inline bool operator==(const BasicString<TCHAR>& left, const BasicString<TCHAR>& right)
	{
		return left.Compare(right) == 0;
	}

	template <typename TCHAR>
	inline bool operator==(const BasicString<TCHAR>& left, const TCHAR* right)
	{
		return left.Compare(right) == 0;
	}

	template <typename TCHAR>
	inline bool operator==(const TCHAR* left, const BasicString<TCHAR>& right)
	{
		return right.Compare(left) == 0;
	}

	template <typename TCHAR>
	inline bool operator!=(const BasicString<TCHAR>& left, const BasicString<TCHAR>& right)
	{
		return left.Compare(right) != 0;
	}

	template <typename TCHAR>
	inline bool operator!=(const BasicString<TCHAR>& left, const TCHAR* right)
	{
		return left.Compare(right) != 0;
	}

	template <typename TCHAR>
	inline bool operator!=(const TCHAR* left, const BasicString<TCHAR>& right)
	{
		return right.Compare(left) != 0;
	}

	template <typename TCHAR>
	inline BasicString<TCHAR> operator+(const BasicString<TCHAR>& left, const BasicString<TCHAR>& right)
	{
		BasicString<TCHAR> s;
		s._InternalConcat(left._data, left.Length(), right._data, right.Length());
		return s;
	}

	template <typename TCHAR>
	inline BasicString<TCHAR> operator+(const BasicString<TCHAR>& left, TCHAR right)
	{
		BasicString<TCHAR> s;
		s._InternalConcat(left._data, left.Length(), &right, 1);
		return s;
	}

	template <typename TCHAR>
	inline BasicString<TCHAR> operator+(TCHAR left, const BasicString<TCHAR>& right)
	{
		BasicString<TCHAR> s;
		s._InternalConcat(&left, 1, right._data, right.Length());
		return s;
	}

	template <typename TCHAR>
	inline BasicString<TCHAR> operator+(const BasicString<TCHAR>& left, const TCHAR* right)
	{
		BasicString<TCHAR> s;
		s._InternalConcat(left._data, left.Length(), right, BasicString<TCHAR>::trait_type::Length(right));
		return s;
	}

	template <typename TCHAR>
	inline BasicString<TCHAR> operator+(const TCHAR* left, const BasicString<TCHAR>& right)
	{
		BasicString<TCHAR> s;
		s._InternalConcat(left, BasicString<TCHAR>::trait_type::Length(left), right._data, right.Length());
		return s;
	}
}






















//////////////////////////////////////////////////////////////////////////
// string
namespace tpl
{
	// blue string
	template <ksize_t SIZE>
	class BlueStr : public BasicBls<char, SIZE>
	{
	public:
		typedef BasicBls<char, SIZE> super_type;
		typedef BlueStr<SIZE> this_type;
		typedef typename super_type::value_type value_type;
		typedef typename super_type::trait_type trait_type;
		typedef typename super_type::ConstIterator ConstIterator;
		typedef typename super_type::Iterator Iterator;

		BlueStr()
			: super_type()
		{
		}

		template <ksize_t OSIZE>
		BlueStr(const BlueStr<OSIZE>& right)
			: super_type(right._data, right._len)
		{
		}

		BlueStr(const char* str, kint len = -1)
			: super_type(str, len)
		{
		}

		BlueStr(char ch)
			: super_type(ch)
		{
		}

		BlueStr(const kwchar* str, kint len = -1)
			: super_type()
		{
			this->_len = (kint)k_conv_uni_to_utf8(this->_data, SIZE - 1, str, len<0 ? 0 : len);
		}

		BlueStr& operator=(const BlueStr& str)
		{
			super_type::operator=(str);
			return *this;
		}

		BlueStr& operator=(const char* str)
		{
			super_type::operator=(str);
			return *this;
		}

		BlueStr& operator=(char ch)
		{
			super_type::operator=(ch);
			return *this;
		}

		BlueStr& operator=(const kwchar* str)
		{
			this->_len = (kint)k_conv_uni_to_utf8(this->_data, SIZE-1, str, 0);
			return *this;
		}
	};

	template <ksize_t SIZE>
	inline BlueStr<SIZE> operator+(const BlueStr<SIZE>& left, const BlueStr<SIZE>& right)
	{
		BlueStr<SIZE> bs(left);
		bs += right;
		return bs;
	}

	template <ksize_t SIZE>
	inline BlueStr<SIZE> operator+(const BlueStr<SIZE>& left, const char* right)
	{
		BlueStr<SIZE> bs(left);
		bs += right;
		return bs;
	}

	template <ksize_t SIZE>
	inline BlueStr<SIZE> operator+(const BlueStr<SIZE>& left, char right)
	{
		BlueStr<SIZE> bs(left);
		bs += right;
		return bs;
	}

	template <ksize_t SIZE>
	inline BlueStr<SIZE> operator+(const char* left, const BlueStr<SIZE>& right)
	{
		BlueStr<SIZE> bs(left);
		bs += right;
		return bs;
	}

	template <ksize_t SIZE>
	inline BlueStr<SIZE> operator+(char left, const BlueStr<SIZE>& right)
	{
		BlueStr<SIZE> bs(left);
		bs += right;
		return bs;
	}

	//
	template <ksize_t SIZE>
	class Hash <tpl::BlueStr<SIZE> >
	{
	public:
		typedef tpl::BlueStr<SIZE> key_type;

		ksize_t operator()(const key_type& key) const
		{
			return key.Hash();
		}
	};

	//
	template <ksize_t SIZE>
	class EqTo <tpl::BlueStr<SIZE> >
#if defined(_FUNCTIONAL_) || defined(_STL_FUNCTION_H)
		: public std::binary_function<tpl::BlueStr<SIZE>, tpl::BlueStr<SIZE>, bool>
#endif
	{
	public:
		bool operator()(const tpl::BlueStr<SIZE>& left, const tpl::BlueStr<SIZE>& right) const
		{
			return left == right;
		}
	};

	// blue wide string
	template <ksize_t SIZE>
	class BlueWcs : public BasicBls<kwchar, SIZE>
	{
	public:
		typedef BasicBls<kwchar, SIZE> super_type;
		typedef BlueWcs<SIZE> this_type;
		typedef typename super_type::value_type value_type;
		typedef typename super_type::trait_type trait_type;
		typedef typename super_type::ConstIterator ConstIterator;
		typedef typename super_type::Iterator Iterator;

		BlueWcs()
			: super_type()
		{
		}

		template <ksize_t OSIZE>
		BlueWcs(const BlueWcs<OSIZE>& right)
			: super_type(right._data, right._len)
		{
		}

		BlueWcs(const kwchar* str, kint len = -1)
			: super_type(str, len)
		{
		}

		BlueWcs(kwchar ch)
			: super_type(ch)
		{
		}

		BlueWcs(const char* str, kint len = -1)
			: super_type()
		{
			this->_len = (kint)k_conv_utf8_to_uni(this->_data, SIZE - 1, str, len<0 ? 0 : len);
		}

		BlueWcs& operator=(const BlueWcs& str)
		{
			super_type::operator=(str);
			return *this;
		}

		BlueWcs& operator=(const kwchar* str)
		{
			super_type::operator=(str);
			return *this;
		}

		BlueWcs& operator=(kwchar ch)
		{
			super_type::operator=(ch);
			return *this;
		}

		BlueWcs& operator=(const char* str)
		{
			this->_len = (kint)k_conv_utf8_to_uni(this->_data, SIZE - 1, str, 0);
			return *this;
		}
	};

	template <ksize_t SIZE>
	inline BlueWcs<SIZE> operator+(const BlueWcs<SIZE>& left, const BlueWcs<SIZE>& right)
	{
		BlueWcs<SIZE> bs(left);
		bs += right;
		return bs;
	}

	template <ksize_t SIZE>
	inline BlueWcs<SIZE> operator+(const BlueWcs<SIZE>& left, const kwchar* right)
	{
		BlueWcs<SIZE> bs(left);
		bs += right;
		return bs;
	}

	template <ksize_t SIZE>
	inline BlueWcs<SIZE> operator+(const BlueWcs<SIZE>& left, kwchar right)
	{
		BlueWcs<SIZE> bs(left);
		bs += right;
		return bs;
	}

	template <ksize_t SIZE>
	inline BlueWcs<SIZE> operator+(const kwchar* left, const BlueWcs<SIZE>& right)
	{
		BlueWcs<SIZE> bs(left);
		bs += right;
		return bs;
	}

	template <ksize_t SIZE>
	inline BlueWcs<SIZE> operator+(kwchar left, const BlueWcs<SIZE>& right)
	{
		BlueWcs<SIZE> bs(left);
		bs += right;
		return bs;
	}

	//
	template <ksize_t SIZE>
	class Hash <tpl::BlueWcs<SIZE> >
	{
	public:
		typedef tpl::BlueWcs<SIZE> key_type;

		ksize_t operator()(const key_type& key) const
		{
			return key.Hash();
		}
	};

	//
	template <ksize_t SIZE>
	class EqTo <tpl::BlueWcs<SIZE> >
#if defined(_FUNCTIONAL_) || defined(_STL_FUNCTION_H)
		: public std::binary_function<tpl::BlueWcs<SIZE>, tpl::BlueWcs<SIZE>, bool>
#endif
	{
	public:
		bool operator()(const tpl::BlueWcs<SIZE>& left, const tpl::BlueWcs<SIZE>& right) const
		{
			return left == right;
		}
	};

	// string
	typedef BasicString<char> String;

	// wide string
	typedef BasicString<kwchar> WideString;

	//
	template <typename TCHAR>
	class Hash <tpl::BasicString<TCHAR> >
	{
	public:
		typedef tpl::BasicString<TCHAR> key_type;

		ksize_t operator()(const key_type& key) const
		{
			return key_type::trait_type::Hash(key._data, false);
		}
	};

	// string equal
	template <typename TCHAR>
	class EqTo <tpl::BasicString<TCHAR> >
#if defined(_FUNCTIONAL_) || defined(_STL_FUNCTION_H)
		: public std::binary_function<tpl::BasicString<TCHAR>, tpl::BasicString<TCHAR>, bool>
#endif
	{
	public:
		typedef tpl::BasicString<TCHAR> key_type;

		bool operator()(const key_type& left, const key_type& right) const
		{
			return key_type::trait_type::Compare(left._data, right._data, false) == 0;
		}
	};
}
#endif	// __cplusplus

#if _MSC_VER
#pragma warning(pop)
#endif

#endif	// __SBCTN_H__
